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

3 * 3s398

Значення 8, яке отримали при s = 2, присутнє в таблиці 2t, 0  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 S2. Визначимо послідовність елементів xi наступним чином:

x0 = 1, xi+1 = , i 0(1)

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

xi =

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

с0 = 0, сi+1 = , i 0(2)

та

d0 = 0, di+1 = , i 0(3)

Алгоритм буде працювати циклічно шукаючи таке знчення i, для якого xi = x2i. Для таких значень будуть мати місце рівність = або = . Логарифмуючи останню рівність за основою a, матимемо:

(di - d2i) * logab (c2i - ci) mod n

Якщо di  d2i (mod n), то це рівняння може бути ефективно розв’язано для обчислення logab.

Алгоритм

Вхід: генератор a циклічної групи G з порядком n та елемент b G.

Вихід: дискретний логарифм x = logab.

1. x0 1, c0 0, d0 0.

2. for i = 1, 2, ... do

2.1. За значеннями xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).

2.2. if (xi = x2i) then

r (di - d2i) mod n;

if (r = 0) then return (FALSE);// розв’язку не знайдено