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^[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 ${\displaystyle \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.^[2]​

El algoritmo

Sea ${\displaystyle G}$  un grupo cíclico. El algoritmo tiene como entrada dos elementos ${\displaystyle g,h\in G}$  y como salida ${\displaystyle x\in \mathbb {N} }$  tal que ${\displaystyle 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, ${\displaystyle G=S_{1}\cup S_{2}\cup S_{3}}$ , de forma que el neutro del grupo no pertenezca a ${\displaystyle S_{2}}$ , con ${\displaystyle S_{1},S_{2},S_{3}}$  aproximadamente del mismo tamaño. Se define la sucesión ${\displaystyle (x_{k},a_{k},b_{k})}$  en ${\displaystyle G\times \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$  inductivamente:

${\displaystyle (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 ${\displaystyle k\in \mathbb {N} }$  se tiene ${\displaystyle x_{k}=g^{a_{k}}h^{b_{k}}}$ . El objetivo del algoritmo es encontrar ${\displaystyle l\neq t}$  tales que ${\displaystyle x_{l}=x_{t}}$ . En ese caso tendremos ${\displaystyle g^{a_{l}}h^{b_{l}}=g^{a_{t}}h^{b_{t}}}$ , de donde ${\displaystyle a_{l}-a_{t}=x(b_{t}-b_{l})}$  (mod n). Si ${\displaystyle b_{t}-b_{l}}$  es coprimo con n, podemos de aquí deducir el valor de x.

Para encontrar ${\displaystyle l\neq t}$  tales que ${\displaystyle 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 ${\displaystyle 1,37{\sqrt {n}}}$  para el caso en que el grupo es ${\displaystyle \mathbb {Z} _{n}^{*}}$ .^[3]​

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",^[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.^[3]​

Referencias

1. Pollard, John (1978). «Monte Carlo methods for index computation (mod p)». Mathematics of Computation 32 (143): 918-924. ISSN 0025-5718. doi:10.2307/2006496. Consultado el 31 de octubre de 2015. 
2. S. Bai; R. Brent (2008). «On the Efficiency of Pollard’s Rho Method for Discrete Logarithms». Conferences in Research and Practice in Information Technology 77: 125-131. Consultado el 1 de noviembre de 2015. 
3. Santamaría Fernández, Jennifer (2013). El logaritmo discreto y sus aplicaciones en criptografía (Grado). Universidad de Cantabria. Consultado el 1 de noviembre de 2015. 
4. Brent, Richard (1980). «An improved Monte Carlo factorization algorithm». BIT 20: 176-184. Consultado el 1 de noviembre de 2015. 
5. Teske, Edlyn (2001). «On random walks for Pollard's rho method». Mathematics of computation 70: 809-825. ISSN 1088-6842. Consultado el 1 de noviembre de 2015. 

•   Datos: Q4053693