Algoritmo rho de Pollard (logaritmos discretos)

El algoritmo rho de Pollard para el logaritmo discreto es un algoritmo publicado por el matemático John Pollard en 1978​ 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 $\mathbb {Z} _{p}^{*}$ (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

Sea $G$ un grupo cíclico. El algoritmo tiene como entrada dos elementos $g,h\in G$ y como salida $x\in \mathbb {N}$ tal que $g^{x}=h$. Se supone conocido el orden del grupo, al que notaremos n.

Se realiza una partición de G en tres subconjuntos disjuntos, $G=S_{1}\cup S_{2}\cup S_{3}$, de forma que el neutro del grupo no pertenezca a $S_{2}$, con $S_{1},S_{2},S_{3}$ aproximadamente del mismo tamaño. Se define la sucesión $(x_{k},a_{k},b_{k})$ en $G\times \mathbb {Z} _{n}\times \mathbb {Z} _{n}$ inductivamente:

$(x_{0},a_{0},b_{0})=(e_{G},0,0),\ \ \ \ (x_{k+1},a_{k+1},b_{k+1})=\left\{{\begin{array}{ll}(hx_{k},a_{k},b_{k}+1)&{\mbox{si }}x_{k}\in S_{1}\\(x_{k}^{2},2a_{k},2b_{k})&{\mbox{si }}x_{k}\in S_{2}\\(gx_{k},a_{k}+1,b_{k})&{\mbox{si }}x_{k}\in S_{3}\end{array}}\right.$

La sucesión está hecha de forma tal que para cada $k\in \mathbb {N}$ se tiene $x_{k}=g^{a_{k}}h^{b_{k}}$. El objetivo del algoritmo es encontrar $l\neq t$ tales que $x_{l}=x_{t}$. En ese caso tendremos $g^{a_{l}}h^{b_{l}}=g^{a_{t}}h^{b_{t}}$, de donde $a_{l}-a_{t}=x(b_{t}-b_{l})$ (mod n). Si $b_{t}-b_{l}$ es coprimo con n, podemos de aquí deducir el valor de x.

Para encontrar $l\neq t$ tales que $x_{l}=x_{t}$ (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 x_i con x_2i.

Orden de ejecución

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 x_i calculamos) y el de "comparaciones" (cuántas veces vemos si x_i=x_2i). 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 x_i y x_2i en cada paso.

Teske realizó investigaciones en las que prueba empíricamente que el número esperado de evaluaciones es aproximadamente $1,37{\sqrt {n}}$ para el caso en que el grupo es $\mathbb {Z} _{n}^{*}$.​

Variantes del algoritmo

Richard Brent publicó un artículo en 1980 en el que realiza una variante en el método para hallar la "colisión",​ que disminuye el número de evaluaciones que se realizan, aumentando el de comparaciones.​

Otra variante fue publicada por Edlyn Teske en 2000.​ 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.​

Referencias

• Datos: Q4053693