Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
8. Дискретное логарифмированиеПусть
разрешимо относительно х при любом В параграфе 2 мы описали алгоритм, позволяющий по заданному числу х достаточно быстро вычислять Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях (см. главу 1). Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения Говоря о сложности задачи дискретного логарифмирования, мы имели в виду «общий случай». Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если Пусть Допустим, что
Так как выполняется сравнение
и положим
означающие справедливость (23) при При Целое число а есть первообразный корень по модулю
Если В случае обычных логарифмов в поле действительных чисел имеется специальное основание
Логарифмы по произвольному основанию с могут быть вычислены с помощью тождества
В случае дискретных логарифмов нет основания, по которому логарифмы вычислялись бы столь же быстро, как натуральные в поле действительных чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными основаниями, остается справедливой и позволяет выбирать основание удобным способом. Единственное условие для этого состоит в том, чтобы логарифм нового основания Так как поле
где
А если выполняются сравнения
то
и
Имея достаточно много векторов Мы опишем ниже реализацию этой идеи, взятую из работы [18]. Эвристические соображения позволили авторам [18] утверждать, что предложенный ими алгоритм требует Положим
Тогда
Если числа а не очень велики, скажем Обозначим через Перебрав все
пар, для которых правая часть сравнения (32) полностью раскладывается на простые сомножители, меньшие Напомним, что число а, согласно нашему предположению, существенно меньше, чем Заметим, что количество (33) найденных сравнений типа (29) превосходит число чем неизвестных. Конечно, множество ее решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система все таки имеет единственное решение, и, решив ее, можно определить дискретные логарифмы всех чисел Как было отмечено, каждое из чисел, стоящих в правой части сравнения (32), не превосходит Вместо перебора всех допустимых значений с, в [18] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть (32) заведомо не раскладывается в произведение малых простых сомножителей. Для каждого
Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел Итак, после первого этапа работы алгоритма в нашем распоряжении оказываются дискретные логарифмы всех чисел из множества
такое разложение, где Наконец, на последнем этапе производится вычисление логарифмов всех чисел Обозначим
Для любых целых чисел
Отметим, что правая часть этого сравнения не превосходит Существуют и другие способы построения соотношений (28). В [23] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношениях типа (28) используются не только простые числа, но и простые идеалы с небольшой нормой. Задача вычисления дискретных логарифмов может рассматриваться также и в полях
|
1 |
Оглавление
|