Дискретний логарифм, Детальна інформація

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

\xF020\xF0F9 = 4;

L1: 1, 24 \xF0BA 3, 28 \xF0BA 9, 212 \xF0BA 1, 216 \xF0BA 3;

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

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

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

\xF020\xF0F9\xF020, 0 \xF0A3 s, t < a) переписати у вигляді b * (g-a)s = gt. Обчислимо g-a та складемо таблицю значень gt, 0 \xF0A3 t < a. Далі починаємо знаходити значення b * (g-a)s, s = 0, 1, … перевіряючи їх наявність у таблиці gt. Як тільки знаходяться такі s та t, алгоритм зупиняється.

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

\xF020\xF0F9 = 5:

t 0 1 2 3 4

2t 1 2 4 8 16



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

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

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

s 0 1 2

3 * 3s 3 9 8



Значення 8, яке отримали при s = 2, присутнє в таблиці 2t, 0 \xF0A3 t < 5.

Звідси 3 * (2-5)2 = 23 або 3 = (25)2 * 23 = 25*2+3 = 213.

Відповідь: 3 = 213, тобто log23 = 13.

Алгоритм Полард - ро

Нехай G – циклічна група з порядком n (n – просте). Розіб’ємо елементи групи G на три підмножини S1, S2 та S3, які мають приблизно однакову потужність. При цьому необхідне виконання умови: 1 \xF0CF\xF020S2. Визначимо послідовність елементів xi наступним чином:

, i \xF0B3\xF0200 (1)

Ця послідовність у свою чергу утворить дві послідовності ci та di , що задовольняють умові



та визначаються наступним чином:

, i \xF0B3\xF0200 (2)

та

, i \xF0B3\xF0200 (3)