Algoritmo rho de Pollard para logaritmos

El algoritmo rho de Pollard para logaritmos es un algoritmo introducido por John Pollard en 1978 para resolver el problema del logaritmo discreto , análogo al algoritmo rho de Pollard para resolver el problema de la factorización de enteros .

El objetivo es calcular${\displaystyle \gamma }$de tal manera que${\displaystyle \alpha ^{\gamma }=\beta }$, dónde${\displaystyle \beta }$pertenece a un grupo cíclico${\displaystyle G}$generado por${\displaystyle \alpha }$El algoritmo calcula números enteros .${\displaystyle a}$,${\displaystyle b}$, ${\displaystyle A}$, y${\displaystyle B}$de tal manera que${\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}}$. Si el grupo subyacente es cíclico de orden${\displaystyle n}$, sustituyendo${\displaystyle \beta }$como${\displaystyle {\alpha }^{\gamma }}$y observando que dos potencias son iguales si y solo si los exponentes son equivalentes módulo el orden de la base, en este caso módulo${\displaystyle n}$, lo entendemos${\displaystyle \gamma }$es una de las soluciones de la ecuación${\displaystyle (Bb)\gamma =(aA){\pmod {n}}}$Las soluciones a esta ecuación se obtienen fácilmente utilizando el algoritmo euclidiano extendido .

Para encontrar lo necesario${\displaystyle a}$,${\displaystyle b}$, ${\displaystyle A}$, y${\displaystyle B}$El algoritmo utiliza el algoritmo de búsqueda de ciclos de Floyd para encontrar un ciclo en la secuencia.${\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}$, donde la función${\displaystyle f:x_{i}\mapsto x_{i+1}}$se supone que tiene un aspecto aleatorio y, por lo tanto, es probable que entre en un bucle de longitud aproximada${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$después${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$pasos. Una forma de definir dicha función es utilizar las siguientes reglas: Partición${\displaystyle G}$en tres subconjuntos disjuntos${\displaystyle S_{0}}$,${\displaystyle S_{1}}$, y${\displaystyle S_{2}}$de tamaño aproximadamente igual utilizando una función hash . Si${\displaystyle x_{i}}$está en${\displaystyle S_{0}}$luego duplica ambos${\displaystyle a}$y${\displaystyle b}$; si${\displaystyle x_{i}\in S_{1}}$luego incrementar${\displaystyle a}$, si${\displaystyle x_{i}\in S_{2}}$luego incrementar${\displaystyle b}$.

Dejar${\displaystyle G}$ser un grupo cíclico de orden${\displaystyle n}$y dado${\displaystyle \alpha ,\beta \in G}$y una partición${\displaystyle G=S_{0}\cup S_{1}\cup S_{2}}$, dejar${\displaystyle f:G\to G}$ser el mapa

${\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}}.}$

Si este mapa se aplica a${\displaystyle x=\alpha ^{a}\beta ^{b}\in G}$, entonces podemos definir mapas${\displaystyle g:G\times \mathbb {Z} \to \mathbb {Z} }$y${\displaystyle h:G\times \mathbb {Z} \to \mathbb {Z} }$para rastrear los índices de${\displaystyle \alpha }$y${\displaystyle \beta }$del resultado. Estos mapas estarían dados por

${\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}},\qquad {\mbox{y}}\\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}}}$

Entrada: a : un generador de G b : un elemento de G Salida: Un entero x tal que a x = b , o fallo Inicializar i ← 0, a 0 ← 0, b 0 ← 0, x 0 ← 1 ∈ Gbucle 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 ) mientras x i ≠ x 2 ir ← b i − b 2 i si r = 0 devolver error devolver r −1 ( a 2 i − a i ) mod n

Consideremos, por ejemplo, el grupo generado por 2 módulo${\displaystyle N=1019}$(el orden del grupo es${\displaystyle n=1018}$, 2 genera el grupo de unidades módulo 1019). El algoritmo se implementa mediante el siguiente programa en C++ :

#include <stdio.h>const int n = 1018 , N = n + 1 ; /* N = 1019 -- primo */ const int alpha = 2 ; /* generador */ 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 ; }

Los resultados son los siguientes (editados):

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 412 49 101 680 377 860 300 413 50 505 680 378 101 300 415 51 1010 681 378 1010 301 416

Eso es${\displaystyle 2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$y entonces${\displaystyle (416-378)\gamma =681-301{\pmod {1018}}}$, para el cual${\displaystyle \gamma _{1}=10}$es una solución como se esperaba. Como${\displaystyle n=1018}$no es primo , hay otra solución${\displaystyle \gamma _{2}=519}$, para el cual${\displaystyle 2^{519}=1014=-5{\pmod {1019}}}$sostiene.

El tiempo de ejecución es aproximadamente${\displaystyle {\mathcal {O}}({\sqrt {n}})}$. Si se utiliza junto con el algoritmo de Pohlig-Hellman , el tiempo de ejecución del algoritmo combinado es${\displaystyle {\mathcal {O}}({\sqrt {p}})}$, dónde${\displaystyle p}$es el factor primo más grande de${\displaystyle n}$.

• Pollard, JM (1978). "Métodos de Monte Carlo para el cálculo de índices (mod p )". Mathematics of Computation . 32 (143): 918– 924. doi : 10.2307/2006496 . JSTOR 2006496 . 
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). "Capítulo 3" (PDF) . Manual de criptografía aplicada .