¿Por qué el Método de Pollard Rho requiere números aleatorios y una función que se comporte de manera pseudo-aleatoria?

Question

Estoy siguiendo "Curvas elípticas: Teoría de números y criptografía" de Lawrence C Washington, y su ejemplo de usar el Método de Pollard Rho para resolver el Problema del Logaritmo Discreto de la Curva Elíptica, lo que implica definir una función iterativa pseudoaleatoria y buscar ciclos.

Cuando introduce la función, dice

"Sea G un grupo finito de orden N. Elige una función f:GG que se comporte de manera bastante aleatoria. Luego, comienza con un elemento aleatorio $P_0$ y computa las iteraciones $P_(i+1) = f(P_i)$. Dado que G es un conjunto finito, habrá algunos índices $i_0

Luego $P_{(i_0)+1} = f(P_{(i_0)} ) = f(P_{(j_0)}=P_{(j_0)+1}=$ y, de manera similar, $P_{(i_0)+l} = P_{(i_0)+l} $ para todo l 0. Por lo tanto, la secuencia $P_i$ es periódica con periodo $j_0$ $i_0$ (o posiblemente un divisor de $j_0$ $i_0$)."

La parte que no entiendo es lo que sigue.

"Si f es una función aleatoria aleatoriamente elegida (no vamos a precisar esto), entonces esperamos encontrar una coincidencia con $j_0$ a lo sumo una constante veces ${\sqrt N}$. "

¿Qué efecto tiene la 'aleatoriedad' en encontrar coincidencias y el tiempo necesario para hacerlo?

Answer 1

Algunas observaciones:

1. Se necesita un $f$ aleatorio para evitar cosas como las siguientes. Supongamos que $G$ es un grupo cíclico (frecuente en criptografía de curvas elípticas) con generador $g$, y use la función (altamente no aleatoria) $f(x)=gx$. Entonces sabemos de antemano que $P_i=g^i$, y que obtenemos el período completo $N$. Cuando eso sucede, no ayudamos en absoluto a nuestra causa.
2. Pero con una función "aleatoria", la paradoja del cumpleaños entra en juego. Si seleccionamos aleatoriamente $M$ elementos de $G$, es probable que comencemos a ver repeticiones, cuando $M$ es aproximadamente $\sqrt{N}$ (más o menos algún pequeño factor constante). El nombre de la paradoja del cumpleaños proviene del hecho de que en una multitud ligeramente mayor a $\sqrt{365}$ personas a menudo se encuentran dos o más personas que comparten un cumpleaños.

La forma en que Pollard $\rho$ se usa para atacar, por ejemplo, el logaritmo discreto aún requiere que la función $f$ esté definida de manera útil (para permitirnos aprovechar el período descubierto en la resolución del DLP). Según recuerdo, dividen el grupo $G$ en piezas fácilmente identificables pero aleatorias. En cada partición, la función $f$ se define mediante una fórmula relativamente simple que depende de la partición. La aleatoriedad en $f$ proviene entonces de la forma en que se particiona el grupo $G. Consulta los libros de texto para obtener más detalles.