Algoritmo rho de Pollard (logaritmos discretos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.[2]

El algoritmo[editar]

Sea un grupo cíclico. El algoritmo tiene como entrada dos elementos y como salida 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 , con aproximadamente del mismo tamaño. Se define la sucesión en inductivamente:

La sucesión está hecha de forma tal que para cada se tiene . El objetivo del algoritmo es encontrar tales que . En ese caso tendremos , de donde (mod n). Si es coprimo con n, podemos de aquí deducir el valor de x.

Para encontrar 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.

Orden de ejecución[editar]

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]

Variantes del algoritmo[editar]

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[editar]

  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. a b 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. a b 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.