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

Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі 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.

= -1, x1 = 1.

3. Обчислення x2.

1. D. Shanks. Class number, a theory of factorization and genera. In Proc. Symposium Pure Mathematics, vol.20, pp.415-440. American Mathematical Society, 1970.