Алгоритм Поліга – Хелмана ефективно розв’язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.
Нехай g, h Î G, |G| = ps, p – просте. Тоді значення x = log gh можна подати у вигляді:
x = x 0 + x 1 p + x 2 p 2 + … + xs -1 ps -1
Піднесемо рівняння h = gx до степеня ps -1:
= = =
* * * … * = ,
оскільки = 1 (g – генератор групи, ps – її порядок).
Таким чином з рівності = знаходимо x 0.
Далі маючи значення x 0, x 1, …, xi -1 можна обчислити xi з рівняння
=
Приклад. Обчислити log37 в Z17*.
Необхідно розв’язати рівняння 3 x = 7 в групі, порядок якої дорівнює 16 = 24.
Представимо x у двійковій системі числення: x = x 0 + 2 x 1 + 4 x 2 + 8 x 3.
1. Обчислення x 0.
Піднесемо рівняння 3 x = 7 до степеня 23 = 8:
= 78, = -1,
* * * = -1.
Оскільки 316 (mod 17) º 1, то останнє рівняння прийме вигляд = -1. Враховуючи що 38 (mod 17) º -1, маємо: = -1, x 0 = 1.
2. Обчислення x 1.
Домножимо рівність = 7 на = 3-1 (mod 17) = 6, отримаємо:
= 7 * 6 або = 8.
Піднесемо рівняння до степеня 4: = 84, = -1, x1 = 1.
3. Обчислення x 2.
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.