El algoritmo rho de Pollard para el logaritmo discreto es un algoritmo publicado por el matemático John Pollard en 1978[1] que permite resolver el problema del logaritmo discreto en cualquier grupo.
La idea para este algoritmo es similar a la que se utiliza en otro para la factorización de enteros, publicado por Pollard en 1975 (algoritmo rho de Pollard).
Existen algoritmos de orden subexponencial para el problema del logaritmo discreto en
(por ejemplo, el algoritmo de cálculo de índices) y el algoritmo de Pollard no lo es, pese a lo cual es útil en la práctica debido a ser simple y efectivo para grupos pequeños.
Además tiene la ventaja de no utilizar nada de la estructura de un grupo particular.
El algoritmo tiene como entrada dos elementos
g , h ∈
tal que
Se supone conocido el orden del grupo, al que notaremos n. Se realiza una partición de G en tres subconjuntos disjuntos,
, de forma que el neutro del grupo no pertenezca a
aproximadamente del mismo tamaño.
Se define la sucesión
inductivamente: La sucesión está hecha de forma tal que para cada
El objetivo del algoritmo es encontrar
tales que
En ese caso tendremos
(mod n).
es coprimo con n, podemos de aquí deducir el valor de x.
tales que
(que se denomina colisión) se utiliza el algoritmo detector de ciclos de Floyd (también conocido como el algoritmo de la liebre y la tortuga).
Consiste en comparar xi con x2i.
Este es un algoritmo que dependiendo de la "suerte" que tengamos puede demorar más o menos tiempo en ejecutarse.
Hay dos cosas que debemos contar a la hora de estudiar el tiempo de ejecución: el número de "evaluaciones" (cuántos xi calculamos) y el de "comparaciones" (cuántas veces vemos si xi=x2i).
Siempre el número de evaluaciones es el triple que el de comparaciones.
La memoria que utiliza el algoritmo es muy pequeña, ya que solo se deben guardar los valores de xi y x2i en cada paso.
Teske realizó investigaciones en las que prueba empíricamente que el número esperado de evaluaciones es aproximadamente
para el caso en que el grupo es
[3] Richard Brent publicó un artículo en 1980 en el que realiza una variante en el método para hallar la "colisión",[4] que disminuye el número de evaluaciones que se realizan, aumentando el de comparaciones.
[2] Otra variante fue publicada por Edlyn Teske en 2000.
[5] Este método reduce el número de iteraciones, con un aumento en el número de comparaciones así como en el uso de memoria.