Алгоритм Полига-Хеллмана.

Этот алгоритм использует следующий подход: пусть G – группа порядка n, и n= - каноническое разложение на простые сомножители. Если x=log_ga mod n, то, вычислив x_i=log_ga mod , для 1 ≤ i ≤ k, можно восстановить x, используя китайскую теорему об остатках.

Для того чтобы вычислить x_i, вычисляют коэффициенты l₀, l₁,…, в p_i-чном представлении числа x_i: x_i=l₀+l₁p_i+…+ , где 0 ≤ l_j ≤ p_i—1.

Представим метол Полига-Хеллмана следующим алгоритмом:

Алгоритм Полига-Хеллмана:

Вход: g – порождающий элемент циклической группы порядка n, a G.

Ш.1. Найти каноническое разложение n= .

Ш.2. Для i от 1 до k выполнить следующие действия:

1. Задать q=p_i, α=α_i.

2. Задать γ=1, l_-1=0.

3. Вычислить .

4. Для j от 1 до α—1 выполнить:

4.1. Вычислить γ=γ ,

4.2. Вычислить l_i= . (например, используя алгоритм «шаг младенца - шаг великана» или прямой поиск).

5. Вычислить x_i=l₀+l₁q+…+l_α—1q^α—1.

Ш.3. Используя Китайскую теорему об остатках, решить систему сравнений x≡x_i(mod ) .

Выход. x=log_ga mod n.

Замечание. Все вычисления производятся в группе G кроме случаев, когда оговорено иное.

Замечание. Поскольку порядок элемента (в чем нетрудно убедиться, подставив вместо его выражение из 4.2 и учитывая, что порядок есть q), то l_i= .

Заметим, что вычисление логарифма прямым поиском на этапе 4.2. происходит сравнительно быстро, так как приходится перебирать не более q значений.

Данный метод эффективен в случаях, когда n является большим числом, а все его простые сомножители – малыми числами.

Сложность данного алгоритма составляет O( ) умножений в группе при условии, что разложение n известно.

Пример.

Пусть G=Z^*_p, p=61, g=2, a=7.

Ш.1. n=φ(p)=p—1=60=2²·3·5.

Ш.2.

1. q=2, α=2.

2. γ=1, l_-1=0.

3. =2³⁰ mod 61=60.

4. j=0 γ=1, =7³⁰ mod 61 = 60 l₀=log₆₀60 mod 61=1.

j=1 γ=2, =(7·2^-1)³⁰mod 61=(7·31)³⁰mod 61=1 l₀=log₆₀1 mod 61=0.

5. x₁=1+0·2=1.

1. q=3, α=1.

2. γ=1, l_-1=0.

3. =2²⁰ mod 61=47.

4. j=0 γ=1, =7²⁰ mod 61 = 47 l₀=log₄₇47 mod 61=1.

5. x₂=1.

1. q=5, α=1.

2. γ=1, l_-1=0.

3. =2¹² mod 61=9.

4. j=0 γ=1, =7¹² mod 61 = 34 l₀=log₉34 mod 61=4 (этот логарифм нашли прямым перебором).

5. x₃=4.

Ш.3. Составим и решим систему . Решением этой системы будет x≡48 (mod 60).

Проверка: 2⁴⁸mod 61=7.

Ответ: log₂7 mod 60 = 48.