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

Її розв’язком буде:

log22 = 1, log23 = 13, log25 = 16

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

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

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

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

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

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

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

Нехай g, h \xF0CE 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:

= -1,

= -1.

= -1, x0 = 1.

2. Обчислення x1.

= 3-1 (mod 17) = 6, отримаємо:

= 8.