Выше мы описали алгоритм, позволяющий по заданному числу x достаточно быстро вычислять ах mod p. Обратная же операция – вычисление по заданному b его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях. Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения exp(c(ln p)1/3(ln ln p)2/3) арифметических операций, где c – некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез.

Говоря о сложности задачи дискретного логарифмирования, мы имели в виду «общий случай». Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если p – 1 есть произведение малых простых чисел.

Пусть q – простое число, делящее р – 1. Обозначим с º а(p – 1)/q (mod p), тогда классы вычетов 1, с, с2, … , сq – 1 все различны и образуют полное множество решений уравнения хq = 1 в поле Fp = Z/Zp. Если q не велико и целое число d удовлетворяет сравнению хq º 1 (mod p), то показатель k, 0 £ k < q, для которого выполняется d º ck (mod p), легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.

Допустим, что р – 1 = qkh, (q,h) = 1. Алгоритм последовательно строит целые числа 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 + e, где 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 + e при некотором e > 0, то правая часть сравнения (12) не превосходит p1/2 + e/2. Можно доказать, что случайно выбранное натуральное число x < p1/2 + e/2 раскладывается в произведение простых чисел, меньших с вероятностью, большей, чем L-1/2 - e/2.

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