Быстрые вычисления с целыми числами и полиномами (стр. 5 из 5)

Мы опишем ниже реализацию этой идеи, взятую из работы [1]. Эвристические соображения позволили авторам этой работы утверждать, что предложенный ими алгоритм требует L^{1 + e}, где L = , арифметических операций для вычисления Log b.

Положим

H = [ ] + 1, J = H² – q.

Тогда 0 < J < 2 + 1, и, как легко проверить, для любой пары целых чисел с₁, с₂ выполняется сравнение

(H + c₁) (H + c₂) º J + (c₁ + c₂)H + c₁c₂ (mod p). (12)

Если числа c_i не очень велики, скажем c_i£ L^{1/2 + e} при некотором e > 0, то правая часть сравнения (12) не превосходит p^{1/2 + e/2}. Можно доказать, что случайно выбранное натуральное число x < p^{1/2 + e/2} раскладывается в произведение простых чисел, меньших с вероятностью, большей, чем L^{-1/2 - e/2}.

Обозначим через S = {q₁,…,q_s} совокупность всех простых чисел q < L^1/2, а также всех простых чисел вида H + c при 0 < c< L^{1/2 + e}. Тогдаs = O(L^{1/2 + e}). Будем теперь перебирать случайным образом числа и для каждой такой пары пытаться разложить на множители соответствующее выражение из правой части (12). Для разложения можно воспользоваться, например, делением на все простые числа, меньшие, чем L^1/2. Перебрав все (L^{1/2 + e})²/2 = O(L^{1 + 2e}) указанных пар с¹, с² мы найдём, как это следует из указанных выше вероятностных соображений, не менее

L^{-1/2 - e/2} *O(L^{1 + 2e} ) = O(L^{1/2 + 3e/2}) (13)

пар, для которых правая часть сравнения (12) полностью раскладывается на простые сомножители, меньшие L^1/2. Сравнение (12), таким образом, принимает вид (8). Так строится система уравнений типа (9).

Напомним, что число а, согласно нашему предположению, существенно меньше, чем L^1/2. Поэтому оно раскладывается в произведение простых чисел, входящих во множество {q₁,…,q_s}, и это приводит к сравнению (10).

Заметим, что количество (13) найденных сравнений типа (9) превосходит число s. Следовательно, построенная система неоднородных линейных сравнений относительно Log q_i содержит сравнений больше, чем неизвестных. Конечно, множество её решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система имеет всё-таки единственное решение, и, решив её, можно определить дискретные логарифмы всех чисел q_i. На этом завершается первый этап работы алгоритма из [1].

Как было отмечено, каждое из чисел, стоящих в правой части сравнения (12), не превосходит p^{1/2 + e/2}. Поэтому оно раскладывается в произведение не более O(lnp) простых сомножителей и, следовательно, каждое из сравнений (9) построенной системы содержит лишь O(lnp) отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для её решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.

Вместо перебора всех допустимых значений c_i в [1] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть (12) заведомо не раскладывается в произведение малых простых сомножителей. Для каждого c₁ и каждой малой простой степени q' < L^1/2 можно найти все решения c² < L^1/2 линейного сравнения

J + (c₁ + c₂)H + c₁c₂º 0 (mod q').

Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел c_1,c₂ и даёт разложение на простые сомножители правых частей сравнений (12).

Итак, после первого этапа работы алгоритма в нашем распоряжении оказываются дискретные логарифмы всех чисел из множества S. Второй этап алгоритма сводит поиск дискретного логарифма числа b к поиску логарифмов некоторого множества чисел u, не превосходящих по величине L². Выбирая случайным образом число w не более L^1/4 раз, можно, как показывают вероятностные соображения, найти такое w, что вычет a^wb mod p раскладывается в произведение простых чисел, меньших L². Пусть

(mod p)

такое разложение, где u₁,…,u_t – некоторые простые числа с условием L^1/2 < u < < L². На поиск этого сравнения потребуется O(L^1/2)арифметических операций. В результате вычисление дискретного логарифма числа b сводится к вычислению t дискретных логарифмов для чисел u_j, 1 £j£t среднего размера.

Наконец, на последнем этапе производится вычисление логарифмов всех чисел u_j. Пусть u – простое число из интервала условием L^1/2 < u < L². Обозначим

G = [Öp / u], I = HGu – p.

Для любых целых чисел c₁, c₂ < L^{1/2 + e} выполняется сравнение

(H + c₁) (H + c₂)uºI + (c₁G+ c₂H + c₁c₂ )u (mod p). (14)

Отметим, что правая часть этого сравнения не превосходит p^1/2 L^{5/2 + e}. Просеивая все числа c₁, c₂ из указанного интервала, можно найти такие, что числа G+ c₂ и правая часть сравнения (14) состоят из простых сомножителей, не превосходящих L^1/2. Тогда сравнение (14) позволяет вычислить Log u. Вычисление Log b при известных уже значениях Log q₁ требует L^{1/2 + e} арифметических операций.

Существуют и другие способы построения соотношений (8). В [2] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношения типа (8) используются не только простые числа, но и простые идеалы с небольшой нормой.

Задача вычисления дискретных логарифмов может рассматриваться также и в полях Fpⁿ, состоящих из pⁿ элементов, в мультипликативных группах классов вычетов (Z/mZ)*, в группах точек эллиптических кривых и вообще в произвольных группах.

Список литературы

1. Введение в криптографию под общей редакцией Ященко, М.: МЦНМО: «Черо», 1999.

2. Алгебраическая алгоритмика, Ноден П., Китте К., М.: «Мир», 1999.

[1]Coppersmith D., Odlyzko A. M., Schroeppel R. Descrete logarithms in GF(p) // Algorithmica. V. 1,1986. P. 1-15.

[2]Lenstra A. K, Lenstra H. W. (jr.) The Development of the Number Field Siev. Lect. Notes in Math. V. 1554. Springer, 1993.

[3]McCarthy D. P. “The optimal algorithm to evaluate xⁿ using elementary multiplication methods”, Math. Comp., vol. 31, n^o 137, 1977, pp. 251 – 256.