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

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

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

x = x ₀ + x ₁ p + x ₂ p ² + … + x_{s -1} p^{s -1}

Піднесемо рівняння h = g^x до степеня p^{s -1}:

 =  =  =

 *  *  * … *  = ,

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

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

Далі маючи значення x ₀, x ₁, …, x_{i -1} можна обчислити x_i з рівняння

 =

Приклад. Обчислити log₃7 в Z₁₇^*.

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

Представимо x у двійковій системі числення: x = x ₀ + 2 x ₁ + 4 x ₂ + 8 x ₃.

1. Обчислення x ₀.

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

 = 7⁸,  = -1,

 *  *  *  = -1.

Оскільки 3¹⁶ (mod 17) º 1, то останнє рівняння прийме вигляд  = -1. Враховуючи що 3⁸ (mod 17) º -1, маємо:  = -1, x ₀ = 1.

2. Обчислення x ₁.

Домножимо рівність  = 7 на  = 3^-1 (mod 17) = 6, отримаємо:

 = 7 * 6 або  = 8.

Піднесемо рівняння до степеня 4:  = 8⁴,  = -1, x₁ = 1.

3. Обчислення x ₂.

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.