En teoría numérica computacional y álgebra computacional , el algoritmo canguro de Pollard (también el algoritmo lambda de Pollard , ver Nombrar más abajo) es un algoritmo para resolver el problema del logaritmo discreto . El algoritmo fue introducido en 1978 por el teórico de números JM Pollard , en el mismo artículo que su más conocido algoritmo rho de Pollard para resolver el mismo problema. [1] Aunque Pollard describió la aplicación de su algoritmo al problema del logaritmo discreto en el grupo multiplicativo de unidades módulo a primo p, es de hecho un algoritmo genérico de logaritmo discreto; funcionará en cualquier grupo cíclico finito.
Algoritmo
Suponer es un grupo cíclico finito de orden que es generado por el elemento , y buscamos encontrar el logaritmo discreto del elemento a la base . En otras palabras, uno busca tal que . El algoritmo lambda permite buscar en algún intervalo . Se puede buscar en todo el rango de logaritmos posibles estableciendo y .
1. Elige un conjunto de enteros y definir un mapa pseudoaleatorio.
2. Elija un número entero y calcular una secuencia de elementos de grupo de acuerdo a:
3. Calcular
Observa eso:
4. Comience a calcular una segunda secuencia de elementos de grupo. de acuerdo a:
y una secuencia correspondiente de números enteros de acuerdo a:
- .
Observa eso:
5. Deje de calcular los términos de y cuando se cumple alguna de las siguientes condiciones:
- A) para algunos . Si las secuencias y "colisionar" de esta manera, entonces tenemos:
- y así terminamos.
- B) . Si esto ocurre, el algoritmo no ha podido encontrar . Se pueden realizar intentos posteriores cambiando la elección de y / o .
Complejidad
Pollard da la complejidad temporal del algoritmo como , basado en un argumento probabilístico que se deriva del supuesto de que actúa de forma pseudoaleatoria. Cuando el tamaño del conjuntoa buscar se mide en bits , como es normal en la teoría de la complejidad , el conjunto tiene tamaño, por lo que la complejidad del algoritmo es , que es exponencial en el tamaño del problema. Por esta razón, el algoritmo lambda de Pollard se considera un algoritmo de tiempo exponencial . Para ver un ejemplo de un algoritmo de logaritmo discreto de tiempo subexponencial , consulte el algoritmo de cálculo de índices .
Nombrar
El algoritmo es bien conocido por dos nombres.
El primero es el "algoritmo canguro de Pollard". Este nombre es una referencia a una analogía utilizada en el artículo que presenta el algoritmo, donde el algoritmo se explica en términos del uso de un canguro domesticado para atrapar a un canguro salvaje . Pollard ha explicado [2] que esta analogía se inspiró en un artículo "fascinante" publicado en el mismo número de Scientific American como una exposición del criptosistema de clave pública RSA . El artículo [3] describía un experimento en el que el "coste energético de la locomoción de un canguro, medido en términos de consumo de oxígeno a varias velocidades, se determinaba colocando canguros en una cinta de correr ".
El segundo es el "algoritmo lambda de Pollard". Al igual que el nombre de otro de los algoritmos de logaritmos discretos de Pollard , el algoritmo rho de Pollard , este nombre se refiere a la similitud entre una visualización del algoritmo y la letra griega lambda (). El trazo más corto de la letra lambda corresponde a la secuencia, ya que parte de la posición b a la derecha de x. En consecuencia, la carrera más larga corresponde a la secuencia, que "choca con" la primera secuencia (al igual que los trazos de una lambda se cruzan) y luego la sigue posteriormente.
Pollard ha expresado su preferencia por el nombre "algoritmo canguro", [4] ya que esto evita la confusión con algunas versiones paralelas de su algoritmo rho, que también se han llamado "algoritmos lambda".
Ver también
Referencias
- ^ J. Pollard, métodos de Monte Carlo para el cálculo de índices (mod p) , Matemáticas de la computación, volumen 32, 1978
- ^ JM Pollard, canguros, monopolio y logaritmos discretos , Journal of Cryptology, volumen 13, págs. 437–447, 2000
- ^ TJ Dawson, Kangaroos , Scientific American, agosto de 1977, págs. 78–89
- ^ http://sites.google.com/site/jmptidcott2/