Алгоритм Ро Полларда для логарифмов

Математический алгоритм

Алгоритм ро Полларда для логарифмов — алгоритм, предложенный Джоном Поллардом в 1978 году для решения задачи дискретного логарифмирования , аналогичный алгоритму ро Полларда для решения задачи разложения целых чисел .

Цель состоит в том, чтобы вычислить такое , что , где принадлежит циклической группе, порожденной . Алгоритм вычисляет целые числа , , , и такие, что . Если базовая группа является циклической порядка , то, подставляя как и отмечая, что две степени равны тогда и только тогда, когда показатели степени эквивалентны по модулю порядка основания, в данном случае по модулю , мы получаем, что является одним из решений уравнения . Решения этого уравнения легко получить с помощью расширенного алгоритма Евклида . ${\displaystyle \gamma }$ ${\displaystyle \alpha ^{\gamma }=\beta }$ ${\displaystyle \beta }$ ${\displaystyle G}$ ${\displaystyle \alpha }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}}$ ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle {\alpha }^{\gamma }}$ ${\displaystyle n}$ ${\displaystyle \gamma }$ ${\displaystyle (B-b)\gamma =(a-A){\pmod {n}}}$

Чтобы найти необходимые , , , и алгоритм использует алгоритм поиска цикла Флойда для поиска цикла в последовательности , где функция предполагается случайной и, таким образом, вероятно, войдет в цикл приблизительной длины после шагов. Один из способов определить такую ​​функцию — использовать следующие правила: Разбиение на три непересекающихся подмножества , , и приблизительно равного размера с помощью хэш-функции . Если находится в , то удвоить и ; если , то инкремент , если , то инкремент . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}$ ${\displaystyle f:x_{i}\mapsto x_{i+1}}$ ${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$ ${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$ ${\displaystyle G}$ ${\displaystyle S_{0}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle x_{i}}$ ${\displaystyle S_{0}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle x_{i}\in S_{1}}$ ${\displaystyle a}$ ${\displaystyle x_{i}\in S_{2}}$ ${\displaystyle b}$

Алгоритм

Пусть будет циклической группой порядка , и даны , и разбиение , пусть будет отображением ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \alpha ,\beta \in G}$ ${\displaystyle G=S_{0}\cup S_{1}\cup S_{2}}$ ${\displaystyle f:G\to G}$

${\displaystyle f(x)={\begin{cases}\beta x&x\in S_{0}\\x^{2}&x\in S_{1}\\\alpha x&x\in S_{2}\end{cases}}}$

и определить карты и по ${\displaystyle g:G\times \mathbb {Z} \to \mathbb {Z} }$ ${\displaystyle h:G\times \mathbb {Z} \to \mathbb {Z} }$

${\displaystyle {\begin{aligned}g(x,k)&={\begin{cases}k&x\in S_{0}\\2k{\pmod {n}}&x\in S_{1}\\k+1{\pmod {n}}&x\in S_{2}\end{cases}}\\h(x,k)&={\begin{cases}k+1{\pmod {n}}&x\in S_{0}\\2k{\pmod {n}}&x\in S_{1}\\k&x\in S_{2}\end{cases}}\end{aligned}}}$

вход:  a : генератор G  b : элемент G выход: целое число x такое, что a x = b , или неудачаИнициализировать i ← 0, a 0 ← 0, b 0 ← 0, x 0 ← 1 ∈ Gпетля  i ← i + 1 x i ← f ( x i −1 ), a i ← g ( x i −1 , a i −1 ), b i ← h ( x i −1 , b i −1 ) x 2 i −1 ← f ( x 2 i −2 ), a 2 i −1 ← g ( x 2 i −2 , a 2 i −2 ), b 2 i −1 ← h ( x 2 i −2 , b 2 i −2 ) x 2 i ← f ( x 2 i −1 ), a 2 i ← g ( x 2 i −1 , a 2 i −1 ), b 2 i ← h ( x 2 i −1 , b 2 i −1 ) при этом  x i ≠ x 2 ir ← b i − b 2 i если r = 0 вернуть ошибку вернуть  r −1 ( a 2 i − a i ) mod n

Пример

Рассмотрим, например, группу, сгенерированную 2 по модулю (порядок группы , 2 генерирует группу единиц по модулю 1019). Алгоритм реализуется следующей программой на языке C++ : ${\displaystyle N=1019}$ ${\displaystyle n=1018}$

#include <stdio.h> const int n = 1018 , N = n + 1 ; /* N = 1019 -- простое число */ const int alpha = 2 ; /* генератор */ const int beta = 5 ; /* 2^{10} = 1024 = 5 (N) */                    void new_xab ( int & x , int & a , int & b ) { switch ( x % 3 ) { case 0 : x = x * x % N ; a = a * 2 % n ; b = b * 2 % n ; break ; case 1 : x = x * alpha % N ; a = ( a + 1 ) % n ; break ; case 2 : x = x * beta % N ; b = ( b + 1 ) % n ; break ; } }                                                               int main ( void ) { int x = 1 , a = 0 , b = 0 ; int X = x , A = a , B = b ; for ( int i = 1 ; i < n ; ++ i ) { new_xab ( x , a , b ); new_xab ( X , A , B ); new_xab ( X , A , B ); printf ( "%3d %4d %3d %3d %4d %3d %3d \n " , i , x , a , b , X , A , B ); if ( x == X ) break ; } return 0 ; }                                                         

Результаты следующие (отредактировано):

иксаб XAB------------------------------ 1 2 1 0 10 1 1 2 10 1 1 100 2 2 3 20 2 1 1000 3 3 4 100 2 2 425 8 6 5 200 3 2 436 16 14 6 1000 3 3 284 17 15 7 981 4 3 986 17 17 8 425 8 6 194 17 19............................48 224 680 376 86 299 41249 101 680 377 860 300 41350 505 680 378 101 300 41551 1010 681 378 1010 301 416

То есть и так , для которого есть решение , как и ожидалось. Так как не является простым , есть другое решение , для которого выполняется. ${\displaystyle 2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$ ${\displaystyle (416-378)\gamma =681-301{\pmod {1018}}}$ ${\displaystyle \gamma _{1}=10}$ ${\displaystyle n=1018}$ ${\displaystyle \gamma _{2}=519}$ ${\displaystyle 2^{519}=1014=-5{\pmod {1019}}}$

Сложность

Время выполнения составляет приблизительно . При использовании вместе с алгоритмом Полига–Хеллмана время выполнения комбинированного алгоритма составляет , где — наибольший простой множитель . ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$ ${\displaystyle {\mathcal {O}}({\sqrt {p}})}$ ${\displaystyle p}$ ${\displaystyle n}$

Ссылки

• Поллард, Дж. М. (1978). «Методы Монте-Карло для вычисления индекса (mod p )». Математика вычислений . 32 (143): 918–924. doi :10.2307/2006496. JSTOR  2006496.
• Менезес, Альфред Дж.; ван Ооршот, Пол К.; Ванстоун, Скотт А. (2001). "Глава 3" (PDF) . Справочник по прикладной криптографии .