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 de logaritmos discretos , análogo al algoritmo rho de Pollard para resolver el problema de factorización de enteros .

El objetivo es calcular tal que , donde pertenece a un grupo cíclico generado por . El algoritmo calcula números enteros , , y tales que . Si el grupo subyacente es cíclico de orden , al sustituir as y notar 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 a 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 el , , y necesario, 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 separados , y de tamaño aproximadamente igual utilizando una función hash . Si está dentro, entonces duplica ambos y ; si entonces incrementa , si entonces incrementa . ${\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 aplicació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 número entero x tal que a x = b , o fallaInicializar i ← 0, a 0 ← 0, b 0 ← 0, x 0 ← 1 ∈ Gbucle  yo ← yo + 1 x yo ← f ( x yo −1 ), a yo ← gramo ( x yo −1 , a yo −1 ), segundo yo ← h ( x yo −1 , segundo yo −1 ) x 2 yo −1 ← f ( x 2 yo −2 ), a 2 yo −1 ← gramo ( x 2 yo −2 , a 2 yo −2 ), segundo 2 yo −1 ← h ( x 2 yo −2 , segundo 2 yo −2 ) x 2 yo ← f ( x 2 yo −1 ), un 2 yo ← gramo ( x 2 yo −1 , un 2 yo −1 ), segundo 2 yo ← h ( x 2 yo −1 , b 2 i −1 ) mientras  x i ≠ x 2 ir ← b i − b 2 i si r = 0 retorno fallido retorno  r −1 ( a 2 i − a i ) mod n

Ejemplo

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

#incluir <stdio.h> constante int norte = 1018 , norte = norte + 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 ) { cambiar ( x % 3 ) { caso 0 : x = x * x % N ; a = a * 2 % norte ; segundo = segundo * 2 % norte ; romper ; caso 1 : x = x * alfa % N ; un = ( un + 1 ) % norte ; romper ; caso 2 : x = x * beta % N ; segundo = ( segundo + 1 ) % norte ; romper ; } }                                                               int principal ( vacío ) { 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 ); nuevo_xab ( X , A , B ); nuevo_xab ( X , A , B ); printf ( "%3d %4d %3d %3d %4d %3d %3d \n " , i , x , a , b , X , A , B ); si ( x == X ) romper ; } devolver 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 41249 101 680 377 860 300 41350 505 680 378 101 300 41551 1010 681 378 1010 301 416

Eso es y así , para lo cual es una solución como se esperaba. Como no es primo , existe otra solución , para la 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 usa junto con el algoritmo de 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 .