Дискретний логарифм

3. Побудувати список L2 = b, bg, bg2, ..., bga - 1 (за модулем n);

4. Знайти число z, яке зустрілося в L1 та L2.

Тоді z = bgk = gla для деяких k та l. Звідси b = gla - k = gx; x = la - k.

Два питання постає при дослідженні роботи наведеного алгоритму:

1. Чи завжди знайдеться число, яке буде присутнім в обох списках?

2. Як ефективно знайти значення z?

Запишемо x = sa + t для деяких s, t таких що 0  s, t < a. Тоді b = gx = gsa + t. Домножимо рівність на ga - t, отримаємо: bga - t = gs(a + 1). Значення зліва обов’язково зустрінеться в L2, а справа – в L1.

Відсортуємо отримані списки L1 та L2 за час O(a * log a). За лінійний час проглядаємо списки зліва направо порівнюючи їх голови: якщо вони рівні, то значення z знайдене, якщо ні – то видалити менше число і продовжити перевірку.

Приклад. Розв’язати рівняння: 2x  11 (mod 13).

a =   = 4;

L1: 1, 24  3, 28  9, 212  1, 216  3;

L2: 11, 11 * 2  9, 11 * 22  5, 11 * 23  10;

Число 9 зустрілося в обох списках. 11 * 2  28, 11  27, звідки x = 7.

Відповідь: x = 7.

Інший підхід до реалізації алгоритму великого та малого кроку можна отримати якщо рівність b = gsa + t (a =  , 0  s, t < a) переписати у вигляді b * (g-a)s = gt. Обчислимо g-a та складемо таблицю значень gt, 0  t < a. Далі починаємо знаходити значення b * (g-a)s, s = 0, 1, … перевіряючи їх наявність у таблиці gt. Як тільки знаходяться такі s та t, алгоритм зупиняється.

Приклад. Обчислити log23 в групі Z19* .

3 = 2x = 2sa+1, 3 * (2-a)s = 2t. Складемо таблицю 2t, 0  t <   = 5:

t01234

2t124816

2-1  10 (mod 19), оскільки 2 * 10  1 (mod 19).

Тоді 3 * (2-5)s (mod 19)  3 * (105)s (mod 19)  3 * 3s (mod 19)

Обчислюємо 3 * 3s, s = 0, 1, … :

s012