Метод прямого поиска.

Этот наивный метод является самым трудоемким, он требует O(n) умножений, то есть обладает экспоненциальной сложностью. Состоит он в следующем: вычисляются g⁰, g¹, g²,…, g^p—1 пока не попадется gⁱ≡a(mod p). Полученное i будет искомым дискретным логарифмом i=log_ga (mod p—1).

Пример

p=23, g=5, a=19.

Ответ: log₅19 mod 22 = 15.

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; a G.

Ш.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 до тех пор, пока не найдется совпадение.

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

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

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