Resumen

El método rho de Pollard y su variante paralelizada son actualmente conocidos como los mejores algoritmos genéricos para calcular logaritmos discretos. Sin embargo, al calcular logaritmos discretos en grupos cíclicos de órdenes grandes utilizando el método rho de Pollard, la detección de colisiones siempre es un consumidor elevado de tiempo y espacio. En este documento, presentamos un nuevo algoritmo eficiente de detección de colisiones para el método rho de Pollard. El nuevo algoritmo es más eficiente que el método de punto distinguido previo y puede adaptarse fácilmente a otras aplicaciones. Sin embargo, el nuevo algoritmo no funciona con el método rho paralelizado, pero puede ser paralelizado con el método lambda de Pollard. Además del análisis teórico, también comparamos el rendimiento del nuevo algoritmo con el método de punto distinguido en experimentos con grupos de curvas elípticas. Los experimentos muestran que el nuevo algoritmo puede reducir el número esperado de iteraciones antes de alcanzar una coincidencia de 1.309

• Materias:Modelado matemático Sistemas estocásticos Productos gráficos Ecuaciones matriciales Métodos de descomposición
• Subjects:Mathematical modeling Stochastic systems Graph products Matrix equations Decomposition methods
• Palabras claves:Método rho de Pollard; Algoritmo de detección de colisiones; Logaritmos discretos; Variante paralelizada; Grupos cíclicos; Método de punto distinguido
• Keywords:Pollard"s rho method; Collision detection algorithm; Discrete logarithms; Parallelized variant; Cyclic groups; Distinguished point method