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

log22 = 1, log23 = 13, log25 = 16

4. Обчислення log212.

k = 3: 12 * 23 (mod 19)  1 – не представимо у вигляді добутку чисел з S.

k = 7: 12 * 27 (mod 19)  16 = 24.

log212 + 7  4log22 (mod 18), log212  (4log22 – 7) (mod 18) = 15.

Відповідь: log212 = 15.

Алгоритм Поліга – Хелмана

Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.

Нехай g, h  G, |G| = ps, p – просте. Тоді значення x = loggh можна подати у вигляді:

x = x0 + x1p + x2p2 + … + xs-1ps-1

Піднесемо рівняння h = gx до степеня ps-1:

= = =

* * * … * = ,

оскільки = 1 (g – генератор групи, ps – її порядок).

Таким чином з рівності = знаходимо x0.

Далі маючи значення x0, x1, …, xi-1 можна обчислити xi з рівняння

=

Приклад. Обчислити log37 в Z17*.

Необхідно розв’язати рівняння 3x = 7 в групі, порядок якої дорівнює 16 = 24.

Представимо x у двійковій системі числення: x = x0 + 2x1 + 4x2 + 8x3.

1. Обчислення x0.

Піднесемо рівняння 3x = 7 до степеня 23 = 8:

= 78, = -1,

* * * = -1.

Оскільки 316 (mod 17)  1, то останнє рівняння прийме вигляд = -1. Враховуючи що 38 (mod 17)  -1, маємо: = -1, x0 = 1.