El algoritmo del canguro de Pollard

En teoría de números computacionales y álgebra computacional , el algoritmo canguro de Pollard (también algoritmo lambda de Pollard , ver 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 John M. Pollard , en el mismo artículo que su más conocido algoritmo rho de Pollard para resolver el mismo problema. ^{[1] [2]} Aunque Pollard describió la aplicación de su algoritmo al problema del logaritmo discreto en el grupo multiplicativo de unidades módulo un primo p , es de hecho un algoritmo de logaritmo discreto genérico: funcionará en cualquier grupo cíclico finito.

Algoritmo

Supongamos que es un grupo cíclico finito de orden generado por el elemento , y buscamos encontrar el logaritmo discreto del elemento en base . En otras palabras, se busca tal que . El algoritmo lambda permite buscar en algún intervalo . Se puede buscar en todo el rango de logaritmos posibles estableciendo y . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$ ${\displaystyle x\in Z_{n}}$ ${\displaystyle \alpha ^{x}=\beta }$ ${\displaystyle x}$ ${\displaystyle [a,\ldots ,b]\subset Z_{n}}$ ${\displaystyle a=0}$ ${\displaystyle b=n-1}$

1. Elija un conjunto de números enteros positivos con media aproximada y defina un mapa pseudoaleatorio . ${\displaystyle S}$ ${\displaystyle {\sqrt {b-a}}}$ ${\displaystyle f:G\rightarrow S}$

2. Elija un número entero y calcule una secuencia de elementos del grupo de acuerdo con: ${\displaystyle N}$ ${\displaystyle \{x_{0},x_{1},\ldots ,x_{N}\}}$

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

3. Calcular

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

Observe que:

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

4. Comience a calcular una segunda secuencia de elementos del grupo de acuerdo con: ${\displaystyle \{y_{0},y_{1},\ldots \}}$

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

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

${\displaystyle d_{n}=\sum _{i=0}^{n-1}f(y_{i})}$.

Observe que:

${\displaystyle y_{i}=y_{0}\alpha ^{d_{i}}=\beta \alpha ^{d_{i}}{\mbox{ for }}i=0,1,\ldots ,N-1}$

5. Dejar de computar los términos de y cuando se cumpla cualquiera de las siguientes condiciones: ${\displaystyle \{y_{i}\}}$ ${\displaystyle \{d_{i}\}}$

A) para algunos . Si las secuencias y "colisionan" de esta manera, entonces tenemos: ${\displaystyle y_{j}=x_{N}}$ ${\displaystyle j}$ ${\displaystyle \{x_{i}\}}$ ${\displaystyle \{y_{j}\}}$

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

Y así hemos terminado.

B) . Si esto ocurre, el algoritmo no ha podido encontrar . Se pueden hacer intentos posteriores modificando la opción de y/o . ${\displaystyle d_{i}>b-a+d}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle f}$

Complejidad

Pollard proporciona la complejidad temporal del algoritmo como , utilizando un argumento probabilístico basado en el supuesto de que actúa de forma pseudoaleatoria. Dado que se puede representar mediante bits, esto es exponencial en el tamaño del problema (aunque sigue siendo una mejora significativa con respecto al algoritmo trivial de fuerza bruta que lleva tiempo ). Para ver un ejemplo de un algoritmo de logaritmo discreto de tiempo subexponencial , consulte el algoritmo de cálculo de índices . ${\displaystyle O({\sqrt {b-a}})}$ ${\displaystyle f}$ ${\displaystyle a,b}$ ${\displaystyle O(\log b)}$ ${\displaystyle O(b-a)}$

Nombramiento

El algoritmo es bien conocido por dos nombres.

El primero es el "algoritmo del 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 de utilizar un canguro domesticado para atrapar a un canguro salvaje . Pollard ha explicado ^[3] 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 ^[4] describía un experimento en el que el "costo energético de locomoción de un canguro, medido en términos de consumo de oxígeno a varias velocidades, se determinó 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 hace referencia 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 comienza desde la posición b a la derecha de x. En consecuencia, el trazo más largo 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. ${\displaystyle \lambda }$ ${\displaystyle \{x_{i}\}}$ ${\displaystyle \{y_{i}\}}$

Pollard ha expresado su preferencia por el nombre "algoritmo canguro", ^[5] ya que esto evita la confusión con algunas versiones paralelas de su algoritmo rho, que también se han llamado "algoritmos lambda".

Véase también

• El truco de cartas de Dynkin
• Recuento de Kruskal ^[6]
• Mesa arcoiris

Referencias

1. Pollard, John M. (julio de 1978) [1 de mayo de 1977, 18 de noviembre de 1977]. "Métodos de Monte Carlo para el cálculo de índices (mod p)" (PDF) . Matemáticas de la computación . 32 (143). Departamento de Matemáticas, Investigación de Telecomunicaciones de Plessey, Taplow Court, Maidenhead, Berkshire, Reino Unido: American Mathematical Society : 918–924. ISSN  0025-5718. Archivado (PDF) desde el original el 3 de mayo de 2013 . Consultado el 19 de agosto de 2023 .(7 páginas)
2. van Oorschot, Paul C. ; Wiener, Michael J. (1999). "Búsqueda de colisiones paralelas con aplicaciones criptoanalíticas". Revista de Criptología . 12 (1). Asociación Internacional para la Investigación Criptológica : 1–28. ISSN  0933-2790.
3. Pollard, John M. (10 de agosto de 2000) [23 de enero de 1998, 27 de septiembre de 1999]. "Canguros, monopolio y logaritmos discretos" (PDF) . Revista de criptología . 13 (4). Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Reino Unido: Asociación Internacional de Investigación Criptológica : 437–447. doi :10.1007/s001450010010. ISSN  0933-2790. Archivado (PDF) desde el original el 18 de agosto de 2023. Consultado el 19 de agosto de 2023 .(11 páginas)
4. Dawson, Terence J. (1 de agosto de 1977). "Canguros". Scientific American . Vol. 237, núm. 2. Scientific American, Inc. págs. 78-89. ISSN  0036-8733. JSTOR  24954004.
5. Pollard, John M. "Jmptidcott2". Archivado desde el original el 18 de agosto de 2023. Consultado el 19 de agosto de 2023 .
6. Pollard, John M. (julio de 2000). "El truco de cartas de Kruskal" (PDF) . The Mathematical Gazette . 84 (500). Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Reino Unido: The Mathematical Association : 265–267. ISSN  0025-5572. JSTOR  3621657. 84.29. Archivado (PDF) desde el original el 2023-08-18 . Consultado el 2023-08-19 .(1+3 páginas)

Lectura adicional

• Montenegro, Ravi [en Wikidata] ; Tetali, Prasad V. (2010-11-07) [2009-05-31]. ¿Cuánto tiempo se tarda en atrapar un canguro salvaje? (PDF) . Actas del cuadragésimo primer simposio anual de la ACM sobre teoría de la computación (STOC 2009). págs. 553–560. arXiv : 0812.0789 . doi :10.1145/1536414.1536490. S2CID  12797847. Archivado (PDF) desde el original el 20 de agosto de 2023 . Consultado el 20 de agosto de 2023 .