←предыдущая следующая→
1 2 3 4 5
це-лые числа uj, j = 0,1,…,k, для которых выполняется сравнение
1 (mod p). (3)
Так как выполняется сравнение 1 (mod p), то найдётся целое число u0, для которого (mod p). При таком выборе сравнение (3) с j = 0, оче-видно, выполняется. Предположим, что найдено число uj, удовлетворяющее сравнению (3). Тогда определим t с помощью сравнения
ct (mod p), (4)
и положим. Имеют место сравнения
1 (mod p), (5)
означающие справедливость (3) при j + 1.
При j = k сравнение означает в силу (2), что 1 (mod p). Целое чис-ло а есть первообразный корень по модулю р, поэтому имеем (x – uk)h 0 (mod p – 1) и
x uk (mod qk).
Если , где все простые числа qj малы, то указан-ная процедура позволяет найти вычеты x mod , i = 1,…,s, и, с помощью ки-тайской теоремы об остатках, вычет x mod p – 1, т. е. решить сравнение (2).
В случае обычных логарифмов в поле действительных чисел имеется спе-циальное основание e = 2,171828…, позволяющее достаточно быстро вычис-лять логарифмы с произвольной точностью. Например, это можно делать с по-мощью быстро сходящегося ряда
ln(1+x)/(1 – x) = 2(x + x3/3 + x5/5 + …), |x| < 1. (6)
Логарифмы по произвольному основанию с могут быть вычислены с помощью тождества
logc x = ln x/ ln c. (7)
В случае дискретных логарифмов нет основания, по которому логарифмы вы-числялись бы столь же быстро, как натуральные в поле действительных чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными ос-нованиями, остаётся справедливой и позволяет выбирать основание удобным способом. Единственное условие для этого состоит в том, чтобы логарифм но-вого основания Log c был взаимно прост c p - 1. Тогда в формуле (7) возможно деление по модулю р – 1. Заметим, что это условие будет выполнено, если и только если с – первообразный корень. Из расширенной гипотезы Римана сле-дует, что наименьший первообразный корень по модулю р ограничен величи-ной O(log6 p). Поэтому в дальнейшем для простоты изложения мы будем пред-полагать, что основание а в (2) невелико, именно а = O(log6 p).
Так как поле Fp неполно, вычисление дискретных логарифмов не может ис-пользовать предельный переход и основано на иных принципах. Прежде всего, нужный дискретный логарифм log b вычисляется не сам по себе, а вместе с со-вокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение вида
(mod p), (8)
где qi, ki, mi Z приводит к соотношению между логарифмами
(k1 – m1)Log q1 + … + (ks – ms)Log qs 0 (mod p – 1). (9)
А если выполняются сравнения
a (mod p – 1) b (mod p),
то
r1Log q1 +…+ rsLog qs 1 (mod p – 1) (10)
и
Log b x1Log q1 +…+ xsLog qs (mod p – 1) (11)
Имея достаточно много векторов k1,…,ks, m1,…,ms с условием (8), можно найти решение соответствующей системы сравнений (9), (10). Если эта система имеет единственное решение, то им как раз и будет набор логарифмов Log q1,…,Log qs. Затем с помощью (11) можно найти Log b.
Мы опишем ниже реализацию этой идеи, взятую из работы [1]. Эвристиче-ские соображения позволили авторам этой работы утверждать, что предложен-ный ими алгоритм требует L1 + , где L = , арифметических операций для вычисления Log b.
Положим
H = [ ] + 1, J = H2 – q.
Тогда 0 < J < 2 + 1, и, как легко проверить, для любой пары целых чисел с1, с2 выполняется сравнение
(H + c1) (H + c2) J + (c1 + c2)H + c1c2 (mod p). (12)
Если числа ci не очень велики, скажем ci L1/2 + при некотором > 0, то правая часть сравнения (12) не превосходит p1/2 + /2. Можно доказать, что случайно вы-бранное натуральное число x < p1/2 + /2 раскладывается в произведение простых чисел, меньших с вероятностью, большей, чем L-1/2 - /2.
Обозначим через S = {q1,…,qs} совокупность всех простых чисел q < L1/2, а также всех простых чисел вида H + c при 0 < c < L1/2 + . Тогда s = O(L1/2 + ). Бу-дем теперь перебирать случайным образом числа и для каждой такой пары пы-таться разложить на множители соответствующее выражение из правой части (12). Для разложения можно воспользоваться, например, делением на все про-стые числа, меньшие, чем L1/2. Перебрав все (L1/2 + )2/2 = O(L1 + 2 ) указанных пар с1, с2 мы найдём, как это следует из указанных выше вероятностных сооб-ражений, не менее
L-1/2 - /2 *O(L1 + 2 ) = O(L1/2 + 3/2) (13)
пар, для которых правая часть сравнения (12) полностью раскладывается на простые сомножители, меньшие L1/2. Сравнение (12), таким образом, принимает вид (8). Так строится система уравнений типа (9).
Напомним, что число а, согласно нашему предположению, существенно меньше, чем L1/2. Поэтому оно раскладывается в произведение простых чисел, входящих во множество {q1,…,qs}, и это приводит к сравнению (10).
Заметим, что количество (13) найденных сравнений типа (9) превосходит число s. Следовательно, построенная система неоднородных линейных сравне-ний относительно Log qi содержит сравнений больше, чем неизвестных. Ко-нечно, множество её решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система имеет всё-таки единствен-ное решение, и, решив её, можно определить дискретные логарифмы всех чисел qi. На этом завершается первый этап работы алгоритма из [1].
Как было отмечено, каждое из чисел, стоящих в правой части сравнения (12), не превосходит p1/2 + /2. Поэтому оно раскладывается в произведение не более O(ln p) простых сомножителей и, следовательно, каждое из сравнений (9) построенной системы содержит лишь O(ln p) отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для её решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.
Вместо перебора всех допустимых значений ci в [1] предлагается использо-вать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть (12) заведомо не раскладывается в произведение малых простых сомножителей. Для каждого c1 и каждой малой простой степени q' < L1/2 можно найти все решения c2 < L1/2 линейного сравнения
J + (c1 + c2)H + c1c2 0 (mod q').
Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел c1,c2 и даёт разложение на простые сомножители правых частей сравнений (12).
Итак, после первого этапа работы алгоритма в нашем распоряжении оказы-ваются дискретные логарифмы всех чисел из множества S. Второй этап алго-ритма сводит поиск дискретного логарифма числа b к поиску логарифмов неко-торого множества чисел u, не превосходящих по величине L2. Выбирая случай-ным образом число не более L1/4 раз, можно, как показывают вероятностные соображения, найти такое , что вычет ab mod p раскладывается в произведе-ние простых чисел, меньших L2. Пусть
(mod p)
такое разложение, где u1,…,ut – некоторые простые числа с условием L1/2 < u < < L2. На поиск этого сравнения потребуется O(L1/2)арифметических операций. В результате вычисление дискретного логарифма числа b сводится к вычислению t дискретных логарифмов для чисел uj, 1 j t среднего размера.
Наконец, на последнем этапе производится вычисление логарифмов всех чисел uj. Пусть u – простое число из интервала условием L1/2 < u < L2. Обозна-чим
G = [p / u], I = HGu – p.
Для любых целых чисел c1, c2 < L1/2 + выполняется сравнение
(H + c1) (H + c2)u I + (c1G+ c2H + c1c2 )u (mod p). (14)
Отметим, что правая часть этого сравнения не превосходит p1/2 L5/2 + . Просеи-вая все числа c1, c2 из указанного интервала, можно найти такие, что числа G+ c2 и правая часть сравнения (14) состоят из простых сомножителей, не превос-ходящих L1/2. Тогда сравнение (14) позволяет вычислить Log u. Вычисление Log b при известных уже значениях Log q1 требует L1/2 + арифметических опе-раций.
Существуют и другие способы построения соотношений (8). В [2] для этого используются вычисления в полях алгебраических чисел. В качестве множите-лей в соотношения типа (8) используются не только простые числа, но и про-стые идеалы с небольшой нормой.
Задача вычисления дискретных логарифмов может рассматриваться также и в полях Fpn, состоящих из pn элементов, в мультипликативных группах классов вычетов (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 xn using elementary multipli-cation methods”, Math. Comp., vol. 31, no 137, 1977, pp. 251
←предыдущая следующая→
1 2 3 4 5