Algoritmo canguro de Pollard

---

En la teoría computacional de números y el álgebra computacional , el algoritmo canguro de Pollard (también el algoritmo lambda de Pollard , consulte Denominación a continuación) 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 algoritmo rho de Pollard, más conocido, 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, de hecho es un algoritmo de logaritmo discreto genérico: funcionará en cualquier grupo cíclico finito.

Supongamos que es un grupo cíclico finito de orden el cual es generado por el elemento , y buscamos encontrar el logaritmo discreto del elemento en 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 posibles logaritmos configurando y . ${\ estilo de visualización G}$${\ estilo de visualización n}$${\ estilo de visualización \ alfa}$${\ estilo de visualización x}$${\ estilo de visualización \ beta}$${\ estilo de visualización \ alfa}$${\ estilo de visualización x \ en Z_ {n}}$${\ estilo de visualización \ alfa ^ {x} = \ beta}$${\ estilo de visualización x}$${\displaystyle [a,\ldots,b]\subconjunto Z_{n}}$${\ estilo de visualización a = 0}$${\ estilo de visualización b = n-1}$

1. Elija un conjunto de enteros y defina un mapa pseudoaleatorio .${\ estilo de visualización S}$${\ estilo de visualización f: G \ flecha derecha S}$

2. Elija un número entero y calcule una secuencia de elementos de grupo según:${\ estilo de visualización N}$${\displaystyle \{x_{0},x_{1},\ldots,x_{N}\}}$

4. Comience a calcular una segunda secuencia de elementos de grupo según:${\displaystyle \{y_{0},y_{1},\ldots \}}$

y una correspondiente secuencia de números enteros según:${\displaystyle \{d_{0},d_{1},\ldots \}}$

---