Алгоритм ро Полларда для логарифмов - это алгоритм, введенный Джоном Поллардом в 1978 году для решения проблемы дискретного логарифмирования , аналогичный алгоритму ро Полларда для решения проблемы целочисленной факторизации .
Цель состоит в том, чтобы вычислить такой, что , где принадлежит циклической группе создан . Алгоритм вычисляет целые числа, , , а также такой, что . Если основная группа циклическая порядка, является одним из решений уравнения . Решения этого уравнения легко получить с помощью расширенного алгоритма Евклида .
Чтобы найти нужное , , , а также алгоритм использует алгоритм поиска цикла Флойда, чтобы найти цикл в последовательности, где функция считается случайным и, следовательно, может войти в цикл примерно через шаги. Один из способов определить такую функцию - использовать следующие правила: Разделить на три непересекающихся подмножества примерно равного размера: , , а также . Если в затем удвойте оба а также ; если затем увеличить , если затем увеличить .
Алгоритм
Позволять быть циклической группой порядка, и учитывая , и перегородка , позволять быть картой и определять карты а также от
вход: a : генератор G b : элемент G выход: целое число x такое, что a x = b , или сбойИнициализировать a 0 ← 0, b 0 ← 0, x 0 ← 1 ∈ Gi ← 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 ← f ( f ( x 2 i -2 )), a 2 i ← g ( f ( x 2 i -2 ), g ( x 2 i -2 , a 2 i -2 )), b 2 i ← h ( f ( x 2 i -2 ), h ( x 2 i -2 , b 2 i -2 )) если x i = x 2 i, то r ← b i - b 2 i if r = 0 вернуть ошибку x ← r −1 ( a 2 i - a i ) mod p вернуть x else // x i ≠ x 2 i i ← я + 1 конец, если конец цикла
Пример
Рассмотрим, например, группу, порожденную 2 по модулю (порядок группы , 2 порождает группу единиц по модулю 1019). Алгоритм реализован следующей программой на C ++ :
#include 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 ; а = а * 2 % п ; b = b * 2 % n ; перерыв ; случай 1 : х = х * альфа % N ; а = ( а + 1 ) % п ; перерыв ; случай 2 : x = x * beta % N ; b = ( b + 1 ) % n ; перерыв ; } }int main ( void ) { int x = 1 , a = 0 , b = 0 ; int X = x , A = a , B = b ; для ( 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 ); если ( x == X ) перерыв ; } return 0 ; }
Результаты следующие (отредактировано):
ixab 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
Это и другие , для которого это решение, как и ожидалось. В виде не простое, есть другое решение , для которого держит.
Сложность
Время работы примерно . При использовании вместе с алгоритмом Полига – Хеллмана время работы комбинированного алгоритма равно, где это наибольший простой фактор .
Рекомендации
- Поллард, Дж. М. (1978). «Методы Монте-Карло для вычисления индекса (mod p )». Математика вычислений . 32 (143): 918–924. DOI : 10.2307 / 2006496 .
- Менезеш, Альфред Дж .; van Oorschot, Paul C .; Ванстон, Скотт А. (2001). «Глава 3» (PDF) . Справочник по прикладной криптографии .