3.2. Шаг младенца – шаг великана.

В открытой литературе этот метод впервые был описан Шенксом (Daniel Shanks), ссылки на него известны с 1973 года. Это был один из первых методов, более быстрый чем метод прямого перебора.

Общая схема алгоритма такова:

Берем два целых числа m и k, таких что mk>p (как правило, m=k=). Затем вычисляются два ряда чисел:

a, ga, g²a, … , g^m—1a (mod p)

g^m, g^2m, g^3m, … , g^km (mod p)

(все вычисления произведены по модулю p).

Найдем такие i и j, для которых gⁱa=g^jm. Тогда x=jm—i.

Справедливость последнего равенства подтверждается следующей цепочкой, все вычисления в которой произведены по модулю p:

g^x=g^jm-i=g^jm(gⁱ)^-1=g^jma(gⁱa)^-1=g^jma(g^jm)^-1=a.

Заметим, что числа i и j непременно будут найдены, поскольку при i=,j=выполняетсяjm—i=, причемkm>p. То есть среди всех чисел вида jm—i обязательно содержится 0 < x ≤ p.

Замечание: Указанный метод можно применять для разыскания дискретных логарифмов в любой циклической группе порядка n.

Приведем этот метод в форме алгоритма.

Алгоритм «Шаг младенца-шаг великана»:

Вход: g - порождающий элемент конечной группы G порядка n; aG.

Ш.1. Вычислить m=.

Ш.2. Вычислить b=g^m.

Ш.3. Вычислить последовательности u_i=bⁱ, v_j=ag^j Для i,j=.

Ш.4. Найти i, j такие что u_i=v_j. x=mi—j mod n. Идти на Выход.

Выход: log_ga=x.

Одна из трудоемких частей этого алгоритма – это поиск на Шаге 4. Он может быть осуществлен несколькими способами:

1. Сначала построить таблицу (i, u_i), отсортировать ее по второй компоненте а затем произволить сравнения по мере нахождения компонент v_j.

2. Построить две таблицы (i, u_i) и (j, v_j), отсортировать каждую из них, а затем произвести поиск совпадений.

3. Объединить u, v в одну таблицу, снабдив их номером в соответствующей последовательности и битом принадлежности к одной из двух последовательностей, а затем применить совместную сортировку. И т. п.

Сложность данного алгоритма составляет O() умножений по модулю и O(log n) операций сравнения.

Пример.

Пусть n=229 (простое число), g=6, a=12.

Ш.1. m=16.

Ш.2. b=g^a mod n =6¹² mod 229 = 183.

Ш.3. В этом примере вычислим сначала ряд u_i, а затем будем вычислять компоненты v_j до тех пор, пока не найдется совпадение.

11	12	13	14	15	16
75	214	3	91	165	196

i=16, j=6. x=mi—j mod n = 250 mod 228 = 22.

Проверка: 6²² mod 229= 12.

Ответ: log₆12 mod 228 = 22.

3.3. Ро-метод Полларда для дискретного логарифмирования.

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

Пусть требуется вычислить log_ga в конечной группе G порядка n.

Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S₁US₂US₃, так чтобы 1S₂. Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой.

Например, если G=Z_p, где p – простое число, то можно задать разбиение S₁={1,…,}, S₂={,…,}, S₃={, … , p—1}, или разбиение может быть таким: если x mod 3=1, то xS₁, если x mod 3=2, то xS₂, если x mod 3=0, то xS₃.

Далее на G задается последовательность x₀, x₁, x₂, … , где x₀=1, x_i+1 вычисляется по x_i посредством функции f для i≥0:

x_i+1=f(x_i)=

Вычисления проводятся в группе G, то есть если G=Z_m, то вычисления следует производить по модулю m.

Такая последовательность групповых элементов может быть представлена двумя последовательностями u₀, u₁, u₂,… и v₀, v₁, v₂,… такими, что x_i=,u₀=v₀=0,

u_i+1=, v_i+1=

Вычисления в последовательностях u и v производятся по модулю n.

В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие x_i и x_2i, что x_i = x_2i. Тогда =. Логарифмируя по основаниюg обе части данного уравнения, получим

(v_i—v_2i)log_ga≡(u_2i—u_i) (mod n)

Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z^*_m, то n=φ(m)).

Сложность данного метода составляет O() , где n – порядок группы G.

Замечание. Метод может дать отказ в том случае, когда v_i =v_2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u₀, v₀ , вычислить x₀=и повторить все шаги алгоритма.

Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как x_i = x_j и дискретный логарифм находится из сравнения (v_i—v_j)log_ga≡(u_j—u_i) (mod n).

Пример.

G=Z^*₁₉, a=8, g=2.

Тогда n=φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда.

Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то xS₁, если x mod 3=2, то xS₂, если x mod 3=0, то xS₃.

Вычисления будут производиться по формулам:

x_i+1=f(x_i)=

u_i+1=, v_i+1=

i	0	1	2	3	4	5	6	7	8
xi	1	8	7	18	17	4	13	9	18
ui	0	0	0	0	1	2	2	2	3
vi	0	1	2	3	3	6	7	8	8
S	S1	S2	S1	S3	S2	S1	S1	S3	S3

x₃=x₈. Логарифм найдем из сравнения (v₃—v₈)log₂8≡(u₈—u₃) (mod 18)

-5 log₂8≡3(mod 18)

13 log₂8≡3(mod 18)

log₂8≡3·7(mod 18)

log₂8≡3(mod 18).

Действительно, 2³≡8 (mod 19).

Ответ: log₂8≡3(mod 18).