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


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

Для того чтобы вычислить xi, вычисляют коэффициенты l0, l1,…, в pi-чном представлении числа xi: xi=l0+l1pi+…+ , где 0 ≤ lj pi1.

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

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

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

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

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

1. Задать q=pi, α=αi.

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

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

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

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

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

5. Вычислить xi=l0+l1q+…+lα1qα—1.

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

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

 

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

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

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

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

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

 

Пример.

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

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

Ш.2.

1. q=2, α=2.

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

3. =230 mod 61=60.

4. j=0 γ=1, =730 mod 61 = 60 l0=log6060 mod 61=1.

j=1 γ=2, =(7·2-1)30mod 61=(7·31)30mod 61=1 l0=log601 mod 61=0.

5. x1=1+0·2=1.

1. q=3, α=1.

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

3. =220 mod 61=47.

4. j=0 γ=1, =720 mod 61 = 47 l0=log4747 mod 61=1.

5. x2=1.

1. q=5, α=1.

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

3. =212 mod 61=9.

4. j=0 γ=1, =712 mod 61 = 34 l0=log934 mod 61=4 (этот логарифм нашли прямым перебором).

5. x3=4.

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

Проверка: 248mod 61=7.

Ответ: log27 mod 60 = 48.

 



Дата добавления: 2018-11-26; просмотров: 866;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.