Método rho de Pollard para logaritmo discreto

El método ro de Pollard para logaritmos discretos ( -method ) es un algoritmo para logaritmos discretos en el anillo de residuos módulo primo, que tiene una complejidad exponencial . Propuesto por el matemático británico John Pollard en 1978 , las ideas básicas del algoritmo son muy similares a las del algoritmo ro de Pollard para la factorización de números . Este método se considera para el grupo de residuos distintos de cero módulo , donde es un número primo mayor que . $\rho$ $pags$ $pags$ $3$

Enunciado del problema del logaritmo discreto

Para un número primo dado y dos enteros y se requiere encontrar un entero que satisfaga la comparación: $pags$ $a$ $b$ $X$

a^x\equiv b\;\pmod{p},

(una)

donde es un elemento del grupo cíclico generado por el elemento . $b$ $GRAMO$ $a$

El algoritmo del método ro

Consideramos una secuencia de pares de enteros módulo y una secuencia de enteros módulo , definidas de la siguiente manera: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $pags$

\{u_i\}, \{v_i\}, \{z_i\},\i\en N,

(2)

u_0=v_0=0,\ z_0=1;

u_{i+1} = \begin{casos} u_i+1\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2u_i\;\bmod\; (p-1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ u_i\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{casos}

(3)

v_{i+1} = \begin{casos} v_i\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2v_i\;\bmod\;(p -1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ v_i+1\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{casos}

(cuatro)

z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}} \pmod{p} = \begin{casos} bz_i\;\bmod\;p, & 0 <z_i<\frac{p}{3};\\ z_i^2\;\bmod\;p, & \frac{p}{3}<z_i<\frac{2}{3}p;\\ az_i \;\bmod\;p, & \frac{2}{3}p<z_i<p; \end{casos}

(5)

Nota: en todas las expresiones, se consideran los residuos no negativos más pequeños.

Nota 2 : en un caso más general, es posible dividir en 3 subconjuntos de una manera ligeramente diferente: dividimos el grupo en tres subconjuntos aproximadamente del mismo tamaño para que no pertenezca al subconjunto . $GRAMO$ $S_1, S_2, S_3$ $una$ $S_{2}$

Dado que cada tercio del segmento al que pertenece un elemento probablemente no esté relacionado con los elementos de las secuencias , la secuencia resultante es pseudoaleatoria. Por lo tanto, pueden existir números y tales que . Si puedes encontrar ese par de números, obtienes: $\{u_i, v_i\}$ $j$ $k$ $z_k = z_j$

b^{u_j}a^{v_j}\equiv b^{u_k}a^{v_k} \pmod{p}.

(6)

Si el número es relativamente primo , entonces esta comparación se puede resolver y se puede encontrar el logaritmo discreto: $u_j - u_k$ $pag-1$

b^{u_j - u_k}\equiv a^{v_k - v_j} \pmod{p}.

x\equiv\log_a{b}\equiv(u_j-u_k)^{-1}(v_k-v_j)\pmod{p-1}.

(7)

Si el máximo común divisor de números y es igual al número , entonces hay una solución a esta comparación por módulo . Deje , entonces, el número deseado , donde puede tomar los valores . Por lo tanto, si es un número lo suficientemente pequeño, el problema se resuelve enumerando todos los valores posibles para . En el peor de los casos, cuando , el método resulta no ser mejor que una enumeración completa de todos los valores posibles para el logaritmo discreto. $u_j - u_k$ $pag-1$ $d > 1$ $X$ $(p - 1) / día$ $x = x_0$ $(mod (p - 1)/d)$ $x = x_0 + m(p - 1)/d$ $metro$ $0, 1, ... , d - 1$ $d$ $metro$ $re = pag - 1$

Para la búsqueda de índices se utiliza el algoritmo de búsqueda del ciclo de Floyd . Al usar este algoritmo, en el paso -th hay valores y se busca un número para el cual . El valor más pequeño en el que se cumple esta condición se denomina epact . Si al mismo tiempo , entonces $j$ $k$ $i$ $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ $i$ $z_i = z_{2i}$ $i$ $(u_{2i}-u_i,\p-1)=1$

x\equiv\log_a{b}\equiv(u_{2i}-u_i)^{-1}(v_{i}-v_{2i})\pmod{p-1 }.

(ocho)

Método Po para un grupo de puntos en una curva elíptica

Sea dado un grupo de puntos de una curva elíptica (EC) . Sin pérdida de generalidad, podemos suponer que y es un número primo. Denote el subgrupo de orden por y fije un elemento generador . Para un elemento arbitrario del grupo , el problema del logaritmo discreto es encontrar el elemento $E(F_p)$ $pag>3$ $pags$ $E(F_p)$ $norte$ $GRAMO$ $PAGS$ $Q=xP$ $1<x<n.$

El grupo se representa como una unión , donde son conjuntos arbitrarios de aproximadamente la misma cardinalidad. La función de iteración se define como $GRAMO$ $G = S_1 \taza S_2 \taza S_3$ $Si$ $f\dos puntos G\to G$

R_{i+1} = f(R_i) = \begin{casos} Q + R_i, & R_i \in S_1; \\ 2R_i, & R_i \en S_2;\\ P + R_i, & R_i \en S_3; \end{casos}

(9)

Así , donde los coeficientes se definen de la siguiente manera $R_i = a_iP + b_iQ$

a_{i+1} = \begin{casos} a_i, & R_i \in S_1; \\ 2a_i, & R_i \in S_2;\\ a_i + 1, & R_i \in S_3; \end{casos}

(diez)

b_{i+1} = \begin{casos} b_i + 1, & R_i \in S_1; \\ 2b_i, & R_i \en S_2;\\ b_i, & R_i \en S_3; \end{casos}

(once)

Al elegir un valor inicial arbitrario , se construyen dos secuencias y hasta que se encuentra una colisión en alguna . Con base en las fórmulas (10) y (11), se resuelve el problema del logaritmo discreto: $R_{0}$ $Rhode Island$ $R_{2i}$ $m : R_m = R_{2m}$

x = \frac{a_{2m} - a_m}{b_m - b_{2m}}

(12)

Es importante que el valor obtenido durante la colisión dependa del valor inicial y determina la complejidad computacional del método de Pollard. $metro$ $R_{0}$

Complejidad del algoritmo

El trabajo principal del algoritmo es calcular secuencias . Estos cálculos requieren tres multiplicaciones de módulo para avanzar a la siguiente iteración. El tamaño de la memoria requerida es mínimo, ya que no es necesario almacenar información sobre todos los elementos anteriores de las secuencias. Así, la complejidad del algoritmo se reduce a la complejidad del problema de encontrar epact que, a su vez, tiene una estimación de complejidad heurística , y para diferentes casos, los valores de la constante pueden ser bastante diferentes, pero, como una regla, mentira dentro . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt p$ $[1;3]$

Comparación con otros algoritmos

En comparación con otros algoritmos de logaritmos discretos , el algoritmo de Pollard es menos costoso tanto en términos de operaciones binarias como en términos de la cantidad de memoria requerida. Por ejemplo, para valores suficientemente grandes del número, este algoritmo es más eficiente en términos de complejidad que el algoritmo COS y el algoritmo Adleman , que tienen complejidad . En comparación con el algoritmo de Shanks , que también tiene complejidad , el algoritmo de Pollard es más ventajoso en relación con la memoria utilizada: el algoritmo de Shanks requiere memoria, mientras que el tamaño de la memoria requerida es constante para este algoritmo (suponiendo que el algoritmo de búsqueda del ciclo de Floyd es usó). $\rho-$ $pags$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Paralelización de métodos

Sistemas de memoria distribuida

La idea del método de Pollard para sistemas de memoria distribuida es separar la iteración de puntos entre estaciones de trabajo cliente y la búsqueda de una colisión por parte del servidor. Si se da un conjunto de estaciones de trabajo cliente, el servidor determina los parámetros comunes al sistema, algún subconjunto , e inicializa las estaciones de trabajo. La estación de trabajo del cliente construye una secuencia de puntos y envía los puntos elemento por elemento al servidor. Si el punto no está en la base de datos, el servidor agrega el punto a la base de datos, de lo contrario, calcula el valor del logaritmo discreto. $\rho-$ $S = \left \{ S_i \mid i = 1 ... r\right \}.$ $D\subconjunto G$ $Si$ $R_{ij} \subconjunto D$

Sistemas de memoria compartida

La idea detrás de este método es paralelizar la función de iteración y el algoritmo de detección de colisiones por separado. La función de iteración se paraleliza en la etapa de cálculo de secuencias y Cabe señalar que el cálculo paralelo de y para un valor fijo y la comparación posterior es ineficiente. Esto se debe al hecho de que la sobrecarga asociada con el uso de flujos es computacionalmente más costosa que la computación Por lo tanto, es recomendable calcular las secuencias de tal manera que la sobrecarga esté nivelada. Esto se puede lograr organizando cálculos de secuencias de la forma y , donde es el tamaño del bloque de cálculo, . La función de detección de colisiones en el método Pollard compara y . Esta comparación se puede paralelizar mediante el uso de un algoritmo de iteración para sistemas de memoria compartida. El resultado de ejecutar la función de iteración de puntos son dos conjuntos de puntos y , que se comparan bloque a bloque, es decir , en el caso de dos núcleos. $Rhode Island$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $yo_{0}$ $R_{2i_0} = f (R_{2i_{0} - 2})$ $\izquierda \{R_{iw+j}\derecha \}^l_{i=0}$ $\izquierda \{R_{2(iw+j)}\derecha \}^l_{i=0}$ $w$ $0 \leqslant j < w, l = \left \lceil \frac{m}{w} \right \rceil$ $\rho-$ $R_m$ $R_{2m}$ $\izquierda \{R_{i}\derecha \}^w_{i=0}$ $\izquierda \{R_{2i}\derecha \}^w_{i=0}$ $R_i = R_{2i}, i = 1 ...\frac{w}{2}$ $R_i = R_{2i}, i = \frac{w}{2} ... w$

Método combinado

El método Pollard para sistemas de memoria distribuida se puede ampliar para su uso en estaciones de trabajo de varios núcleos. La idea del método es que la iteración de puntos por parte de las estaciones de trabajo del cliente ocurra de acuerdo con un cierto algoritmo, cuya esencia es que hay una estación de trabajo del cliente que construye una secuencia de puntos . A continuación, la estación de trabajo selecciona un subconjunto de puntos y lo envía al servidor. La comprobación de pertenencia a un subconjunto se realiza en modo paralelo: y (en el caso de dos núcleos). El servidor agrega puntos y a la base de datos hasta que encuentra un punto ya existente. $\rho-$ $Si$ $\izquierda \{R_{ij}\derecha \}^w_{j=0}$ $Si$ $\izquierda \{ R_{ij}\derecha \}^w_{j=0} \cap D$ $R_{ij} \in D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, yo = \frac{w}{2} ... w$ $\izquierda \{ R_{ij}\derecha \}^w_{j=0} \cap D$

Modificaciones y optimizaciones

Hay varias mejoras significativas en el algoritmo basadas en varios trucos.

Una mejora se describe en [Teske 1998]. La diferencia del método presentado en el documento radica en la complicada función iterativa: contiene 20 ramas diferentes en lugar de las tres descritas anteriormente. Los experimentos numéricos muestran que dicha mejora conduce a una aceleración promedio del algoritmo de caminata aleatoria en un 20 %.

$\Lambda-$ Método de Pollard

En su trabajo sobre el cálculo de logaritmos discretos, Pollard también propuso un método, llamado así porque la forma de una letra griega se parece a la imagen de dos caminos que se unen en uno. La idea del método es ir de dos maneras a la vez: una desde el número cuyo logaritmo discreto se necesita encontrar, la otra desde el número cuyo logaritmo discreto ya se conoce. Si estos dos caminos convergen, es posible encontrar el logaritmo discreto de un número . Pollard sugirió que los pasos en cada camino se consideren como saltos de canguro, razón por la cual este algoritmo a veces se denomina "método canguro". Si se sabe que el logaritmo discreto deseado se encuentra en un intervalo corto, entonces se puede adaptar el método canguro, es decir, usando canguros con saltos más cortos. $\lambda-$ $b$ $B$ $b$

Una propiedad importante del método lambda es el hecho de que se distribuye fácilmente entre varias computadoras. Cada participante en la computación distribuida elige un número aleatorio y comienza a dar pasos pseudoaleatorios a partir del número , donde es el elemento del grupo para el que se busca el logaritmo discreto. Cada participante usa la misma función pseudoaleatoria fácilmente computable , donde hay un conjunto relativamente pequeño de números con un valor promedio comparable al tamaño del grupo , que tiene orden . Los poderes para se calculan por adelantado. Entonces el "vagabundeo", a partir del elemento , toma la forma: $r$ $b^r$ $b$ $f\dos puntos G\to S$ $S$ $GRAMO$ $norte$ $un^s$ $S \ en S$ $b^r$ $w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...$

Deje que el otro participante, eligiendo el número inicial , obtenga la secuencia Si se cruza con la secuencia , es decir, para algunos , entonces, teniendo en cuenta que , se cumple lo siguiente: $r^\principal$ $w^\prime_0, w^\prime_1, w^\prime_2, ...$ $w_0, w_1, w_2, ...$ $w^\prime_i = w_j$ $yo, j$ $b = a^x$

b^{r^\prime}a^{f(w^\prime_0) + f(w^\prime_1) + ... + f(w^\prime_{i-1})} = b^ra^{ f(w_0) + f(w_1) + ... + f(w_{j-1})}

(13)

(r^\prime - r)x \equiv \sum^{j-1}_{\mu=0} {f(w_\mu)} - \sum^{i-1}_{\nu=0} {f(w^\prime_\nu)} \pmod n

(catorce)

Por lo general, este método se usa cuando el orden del grupo es simple. Desde entonces, si todos los números elegidos al comienzo de los cálculos son diferentes en valor absoluto , entonces la comparación se puede resolver fácilmente para encontrar el logaritmo discreto . Una pequeña dificultad es que el partido puede ocurrir dentro de la misma secuencia, lo que significa que . Sin embargo, si el número de participantes en los cálculos es lo suficientemente grande, entonces la probabilidad de coincidencia entre secuencias es mayor que la probabilidad de coincidencia dentro de la misma secuencia. $norte$ $r$ $norte$ $(catorce)$ $X$ $r = r^\primo$

Es posible utilizar una función pseudoaleatoria . En este caso, todas las coincidencias serán útiles: una coincidencia dentro de la misma secuencia también se puede usar para calcular el logaritmo discreto. En el caso de tal coincidencia , el método simplemente se convierte en un método. Sin embargo, si se sabe que el logaritmo discreto deseado se encuentra en un intervalo corto, entonces se puede usar el método original. Entonces, el tiempo de ejecución será aproximadamente la raíz cuadrada de la longitud del intervalo. En este caso, el valor promedio de los números enteros del conjunto debe ser menor para que los "canguros" salten solo en un intervalo de la longitud deseada. $(5)$ $\lambda-$ $\rho-$ $S$

La computadora central debe rastrear todas las secuencias de todos los participantes para los partidos. De acuerdo con la paradoja del cumpleaños , se espera una coincidencia cuando el número de elementos en todas las secuencias es del orden de ). Obviamente, en la forma descrita, este método requiere una gran cantidad de memoria del ordenador central. La siguiente idea, descrita en el trabajo de van Orschot, reduce en gran medida los requisitos de memoria y, por lo tanto, hace que este método sea aplicable para resolver problemas complejos. La idea es considerar los llamados puntos seleccionados. Se supone que los elementos del grupo están representados por números enteros (o posiblemente conjuntos de números enteros). Un campo de longitud binaria distinguida en dicho número consistirá en todos ceros durante aproximadamente la enésima parte del tiempo. Una caminata aleatoria pasará a través de dichos puntos seleccionados en promedio en cada paso. Si dos secuencias aleatorias se cruzan en algún lugar, se cruzarán más y juntas llegarán al siguiente punto seleccionado. Entonces, la idea es enviar solo estos puntos seleccionados a la computadora central, lo que reducirá el tamaño de la memoria requerida por un factor. $O(\raíz cuadrada{n})$ $k$ $1/2k$ $2^k$ $2^k$

Literatura

Vasilenko O. N. Algoritmos de Teoría de Números en Criptografía . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Crandall R., Pomerance K. Números primos. Aspectos criptográficos y computacionales. — M.: URSS, 2011 — P.664. — ISBN 978-5-453-00016-6
Pollard, JM Métodos de Monte Carlo para el cálculo de índices (mod p ). Matemáticas de computación - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Aceleración del método rho de Pollard para calcular logaritmos discretos. Simposio de teoría de números algorítmicos (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Métodos de paralelización del algoritmo Pollard para resolver el problema del logaritmo discreto para sistemas con memoria compartida — 2012
PC van Oorschot, MJ Wiener Búsqueda de colisión paralela con aplicaciones criptoanalíticas - Journal of Cryptology 12 (1) - 1-28 - 1999