4501
правка
Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями
Перейти к навигации
Перейти к поиску
м
Квантовый алгоритм для решения задачи дискретного логарифмирования (посмотреть исходный код)
Версия от 22:42, 14 января 2023
, 14 января 2023→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Логарифмы в группах == Постановка задачи == Пусть даны полож…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны положительные действительные числа a | Пусть даны положительные действительные числа <math>a \ne 1, b</math>. Логарифмом b по основанию a называется единственное действительное число s, такое, что <math>b = a^s</math>. Понятие ''дискретного логарифма'' является расширением этого понятия на общие группы. | ||
Задача 1 (Дискретное логарифмирование) | '''Задача 1 (Дискретное логарифмирование)''' | ||
Дано: группа G; a | Дано: группа G; <math>a, b \in G</math>, такие, что <math>b = a^s</math> для некоторого целого положительного числа s. | ||
Требуется: найти наименьшее положительное целое число s, удовлетворяющее условию b = | Требуется: найти наименьшее положительное целое число s, удовлетворяющее условию <math>b = a^s</math>, также известное как дискретный логарифм b по основанию a в G. | ||
Обычный логарифм соответствует дискретному логарифму над группой положительных вещественных чисел при операции умножения. Наиболее распространенным случаем задачи о дискретном логарифме является группа G = Z*, мультипликативная группа целых чисел от 1 до p - 1 по модулю p, где p – простое число. Еще один важный случай имеет место, когда группа G является группой точек эллиптической кривой над конечным полем. | Обычный логарифм соответствует дискретному логарифму над группой положительных вещественных чисел при операции умножения. Наиболее распространенным случаем задачи о дискретном логарифме является группа <math>G = \mathbb{Z}^*_p</math>, мультипликативная группа целых чисел от 1 до p - 1 по модулю p, где p – простое число. Еще один важный случай имеет место, когда группа G является группой точек эллиптической кривой над конечным полем. | ||
== Основные результаты == | == Основные результаты == | ||