Algoritmo rho de Pollard para logaritmos

Algoritmo matemático

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 factorización de enteros .

El objetivo es calcular de forma que , donde pertenece a un grupo cíclico generado por . El algoritmo calcula números enteros , , y de forma que . Si el grupo subyacente es cíclico de orden , sustituyendo como 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 , obtenemos que es una de las soluciones de la ecuación . Las soluciones de esta ecuación se obtienen fácilmente utilizando el algoritmo euclidiano extendido . ${\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}}}$

Para encontrar los , , , y necesarios, el algoritmo utiliza el algoritmo de búsqueda de ciclos de Floyd para encontrar un ciclo en la secuencia , donde se supone que la función tiene un aspecto aleatorio y, por lo tanto, es probable que entre en un bucle de longitud aproximada después de los pasos. Una forma de definir dicha función es utilizar las siguientes reglas: Partición en tres subconjuntos disjuntos , , y de tamaño aproximadamente igual utilizando una función hash . Si es en entonces duplicar ambos y ; si entonces incrementar , si entonces incrementar . ${\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}$

Algoritmo

Sea un grupo cíclico de orden , y dado , y una partición , sea la función ${\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}}}$

y definir mapas y por ${\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}}}$

entrada:  a : un generador de G  b : un elemento de G salida: Un entero x tal que a x = b , o fallaInicializar 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 devuelve fallo devuelve  r −1 ( a 2 i − a i ) mod n

Ejemplo

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

#incluir <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 ) { caso 0 : x = x * x % N ; a = a * 2 % n ; b = b * 2 % n ; break ; caso 1 : x = x * alfa % N ; a = ( a + 1 ) % n ; break ; caso 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):

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

Es decir y por lo tanto , para lo cual es una solución como se esperaba. Como no es primo , hay otra solución , para lo cual se cumple. ${\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}}}$

Complejidad

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

Referencias

• Pollard, JM (1978). "Métodos de Monte Carlo para el cálculo de índices (mod p )". Matemáticas de la computación . 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 .