Algoritmo del canguro de Pollard

En teoría computacional de números y álgebra computacional , el algoritmo canguro de Pollard (y también el algoritmo lambda de Pollard , consulte la sección Título a continuación) es un algoritmo para resolver el problema del logaritmo discreto . El algoritmo fue propuesto en 1978 por el teórico de números J. M. Pollard en el mismo artículo [1] que su algoritmo ρ más conocido para resolver el mismo problema. Aunque Pollard describe la aplicación de este algoritmo al problema del logaritmo discreto en un grupo multiplicativo módulo a primo p, es, de hecho, un algoritmo general para logaritmos discretos: funcionará en cualquier grupo finito cíclico.

Algoritmo

Sea un grupo cíclico finito de orden generado por un elemento , y buscamos el logaritmo discreto del elemento con respecto a la base . En otras palabras, estamos buscando , tal que . El algoritmo lambda nos permite buscar en algún subconjunto de . Podemos buscar el conjunto completo de logaritmos posibles asumiendo y , aunque el algoritmo ρ será más eficiente en este caso. Procedemos de la siguiente manera: $GRAMO$ $norte$ $\alfa$ $X$ $\beta$ $\alfa$ ${\ estilo de visualización x \ en Z_ {n}}$ ${\ estilo de visualización \ alfa ^ {x} = \ beta}$ $X$ $\{a,\ldots,b\}\subconjunto Z_{n}$ $un=0$ ${\ estilo de visualización b = n-1}$

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

2. Elija un número entero y calcule la secuencia de elementos del grupo de acuerdo con las fórmulas: $norte$ $\{x_{0},x_{1},\ldots,x_{N}\}$

$x_{0}=\alpha ^{b}\,$
${\displaystyle x_{i+1}=x_{i}\alpha ^{f(x_{i)))))$ por $i=0,1,\ldots,N-1$

3. Calcular

d=\sum _{i=0}^{N-1}f(x_{i})

Darse cuenta de

x_{N}=x_{0}\alpha ^{d}=\alpha ^{b+d}\,.

4. Comenzamos a calcular la segunda secuencia de elementos del grupo usando las fórmulas ${\displaystyle \{y_{0},y_{1},\ldots\))$

$y_{0}=\beta\,$
${\displaystyle y_{i+1}=y_{i}\alpha ^{f(y_{i)))))$ por $i=0,1,\ldots,N-1$

y la correspondiente secuencia de números enteros según la fórmula

d_{n}=\sum_{i=0}^{n-1}f(y_{i})

Darse cuenta de

y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}

por

i=0,1,\ldots,N-1

5. Dejar de computar y cuando se cumpla alguna de las condiciones ${\ estilo de visualización \ {y_ {i} \}}$ ${\ estilo de visualización \ {d_ {i} \}}$

A) para algunos . Si las secuencias y "chocan" de esta manera, tenemos:

y_{j}=x_{N}

j

\{x_i\}

{\ estilo de visualización \ {y_ {j} \}}

x_{N}=y_{j}\Rightarrow \alpha ^{b+d}=\beta \alpha ^{d_{j))\Rightarrow \beta =\alpha ^{b+d-d_{j }}{\pmod {n}}\Rightarrow x\equiv b+d-d_{j}{\pmod {n}}

así que encontramos lo que queríamos. B) . Si esto sucede, el algoritmo no ha podido encontrar . Se puede hacer otro intento cambiando el conjunto y/o la asignación .

d_{i}>b-a+d

X

S

F

Dificultad

Pollard especificó una complejidad temporal para el algoritmo , basada en un razonamiento probabilístico, que se deriva de la suposición de que f actúa de forma pseudoaleatoria. Tenga en cuenta que en el caso en que el tamaño del conjunto { a , …, b } se mide en bits , lo cual es habitual en la teoría de la complejidad , el conjunto tiene el tamaño log( b − a ), por lo que la complejidad algorítmica es igual a , que es un exponente del tamaño del problema. Por esta razón, el algoritmo lambda de Pollard se considera un algoritmo de complejidad exponencial . Para ver un ejemplo de un algoritmo subexponencial en el tiempo, consulte Algoritmo de cálculo de pedidos . ${\displaystyle {\scriptstyle O({\sqrt {ba))))))$ ${\scriptstyle O({\sqrt {ba)))=O(2^({\frac {1}{2}}\log(ba))))$

Título

El algoritmo es conocido por dos nombres.

El primer nombre es el algoritmo "canguro" de Pollard . El nombre hace referencia a una analogía utilizada en el artículo donde se proponía el algoritmo. El artículo explica el algoritmo en términos del uso de un canguro domesticado para capturar uno salvaje . Como explicó Pollard [2] , esta analogía se inspiró en un artículo "encantador" publicado en el mismo número de Scientific American que la publicación del RSA Public Key Cryptosystem . El artículo [3] describe un experimento en el que "el costo energético de mover un canguro, medido en términos de consumo de oxígeno a varias velocidades, se determinó colocando un canguro en una cinta rodante ".

El segundo nombre es el algoritmo lambda de Pollard . Muy similar al nombre del otro algoritmo de Pollard para logaritmos discretos, el algoritmo ρ , y este nombre se debe a la similitud de visualización del algoritmo con la letra griega lambda ( ). La línea corta de la letra lambda corresponde a la secuencia . En consecuencia, la línea larga corresponde a la secuencia que "choca con" la primera secuencia (similar al encuentro de las líneas corta y larga de una letra). $\lambda$ $\{x_i\}$ ${\ estilo de visualización \ {y_ {i} \}}$

Pollard prefiere usar el nombre de "algoritmo canguro" [4] para evitar confusiones con algunas versiones paralelas del algoritmo ρ, que también se denominan "algoritmos lambda".

Véase también

mesa arcoiris

Notas

↑ Pollard, 1978 .
↑ Pollard, 2000 , pág. 437-447.
↑ Dawson, 1977 , pág. 78-89.
↑ jmptidcott2 . Consultado el 5 de noviembre de 2016. Archivado desde el original el 17 de agosto de 2016. (indefinido)

Literatura

J. Pollard. Métodos de Monte Carlo para el cálculo de índices mod p // Matemáticas de la Computación. - 1978. - T. 32 .
J. Pollard. Canguros, monopolio y logaritmos discretos // Journal of Cryptology. - 2000. - T. 13 . - S. 437-447 .
TJ Dawson. Canguros // Scientific American. - 1977. - S. 78-89 .

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin