Algoritmo de cálculo de pedidos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de junio de 2019; las comprobaciones requieren 2 ediciones .

El algoritmo de cálculo de orden ( algoritmo de cálculo de índice ) es un algoritmo probabilístico para calcular el logaritmo discreto en un anillo de residuos módulo un número primo . La complejidad de encontrar el logaritmo discreto es la base de muchos algoritmos relacionados con la criptografía . Ya que resolver este problema usando grandes números requiere una gran cantidad de recursos que ninguna computadora moderna puede proporcionar . Un ejemplo de tal algoritmo es GOST R 34.10-2012 .

Historia

Maurice Krajczyk propuso por primera vez la idea básica de este algoritmo en su libro "Théorie des Nombres" en 1922. Después de 1976, el problema del logaritmo discreto se vuelve importante en matemáticas y criptoanálisis. Esto se debe a la creación del criptosistema Diffie-Hellman . En este sentido, en 1977, R. Merkle retomó las discusiones sobre este algoritmo. Dos años más tarde, fue publicado por primera vez por los colegas de Merkel. Finalmente, en 1979, Adlerman lo optimizó, investigó la complejidad y lo presentó en la forma que conocemos hoy. Actualmente, el algoritmo de cálculo de órdenes y sus versiones mejoradas proporcionan la forma más rápida de calcular logaritmos discretos en algunos grupos finitos.

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$ $gramo$ $C$ $X$

g^{x}\equiv c\;{\pmod {p}},

donde es un elemento del grupo cíclico generado por el elemento . $C$ $GRAMO$ $gramo$

Algoritmo

Entrada : g - generador de un grupo cíclico de orden n , a - de un subgrupo cíclico, p - un número primo, c - parámetro de confiabilidad, generalmente tomado igual a 10 o un número cercano a este valor (utilizado para implementar el algoritmo en una computadora, si una persona decide, entonces no se configura).

Tarea : encontrar x tal que . $g^{x}\equiv c$

Elija una base factorial S = { p 1 , p 2 , p 3 , …, p t } (Si G = Z * p , entonces la base consta de los primeros t números primos).
Elevamos g a una potencia aleatoria k , donde k es tal que . obtenemos _ $0\leqslant k<n$ $g^{k}$
Representamos g k de la siguiente manera: $g^{k}=\prod_{i=1}^{t}p_{i}^{a_{i)),$ donde (es decir, estamos tratando de factorizarlo). Si no funciona, vuelve al paso 2. $a_{i}\geqslant 0$
Del párrafo 3 se sigue la expresión $k\equiv \sum_{i=1}^{t}a_{i}\log_{g}p_{i}\mod n,$ obtenido tomando un logaritmo (la comparación se toma módulo el orden del grupo, ya que trabajamos con el exponente, pero en el grupo G ). Los logaritmos son desconocidos en esta expresión. Hay t de ellos. Es necesario obtener tales ecuaciones t + c piezas, si esto no es posible, volvemos al paso 2 (cuando se implementa en una computadora) u obtener el número requerido de ecuaciones para encontrar todos los logaritmos desconocidos (cuando lo resuelve una persona). $g^{n}\equivalente a 1$
Resolvemos el sistema de ecuaciones resultante, con t incógnitas y t + c comparaciones.
Elegimos un número aleatorio k tal que . Calculamos . $0\leqslant k<n$ $cg^{k}$
Repetimos el punto 3, solo para el número . Si no funciona, volvemos al párrafo 6. $cg^{k}$
De manera similar al punto 4, obtenemos: $x=\log_{g}c=\sum_{i=1}^{t}a_{i}\log_{g}p_{i}-k\mod n$ , donde ( ), donde . En este punto, resolvimos el problema del logaritmo discreto encontrando . ${\ estilo de visualización \ registro _ {g} p_ {i}}$ $1\leqslant i\leqslant t$ $k=\log _{g}g^{k}\mod n$ ${\ estilo de visualización x = \ registro _ {g} c}$

Salida : . ${\ estilo de visualización x = \ registro _ {g} c}$

Ejemplo

Resuelve la ecuación: $17\equiv 10^{x}\;(mod47)$

Elige una base factorial Sea k = 7 Calcula $S=\{2,3,5\}$ $g^{k}$

$k=1\;\;\;\;10^{1}mod47=10=2*5$

$k=2\;\;\;\;10^{2}mod47\equiv 6=2*3$

$k=3\;\;\;\;10^{3}mod47\equiv 13$

$k=4\;\;\;\;10^{4}mod47\equiv 36=2*2*3*3$

$k=5\;\;\;\;10^{5}mod47\equiv 31$

$k=6\;\;\;\;10^{6}mod47\equiv 28=2*2*7$

$k=7\;\;\;\;10^{7}mod47\equiv 45=3*3*5$

Tomamos el logaritmo y denotamos Y obtenemos el sistema de ecuaciones $U_{i}=log_{g}p_{i}$ $\left\{{\begin{matriz}U_{1}+U_{3}=1\\U_{1}+U_{2}=2\\2U_{1}+2U_{2}=4\\2U_ {2}+U_{3}=7\end{matriz}}\derecha.$

lo resolvemos

$u_{2}={\frac {8}{3}}(mod46)=8*3^{-1}(mod46)=\{\varphi (46)=\varphi (2*23)\ }=22=8*3^{22}(mod46)\equiv 18$

Efectivamente, por lo tanto , $10^{18}mod47\equiv 3$ $U_{1}=30$ $U_{2}=18$ $U_{3}=17$

Encontramos k tal que $cg^{k}={\displaystyle \prod_{i=1}^{t}p_{i}^{a_{i}}}$

$17*10^{1}(mod47)=29$

$17*10^{2}(mod47)=8=2*2*2$

Como consecuencia $k=2$

Tomamos el logaritmo de esta expresión y obtenemos

$log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46\equiv 42$

Respuesta : $x=42$

Dificultad

En este algoritmo, el número de iteraciones depende tanto del tamaño de p como del tamaño de la base factorial. Pero elegimos la base de factores de antemano y su tamaño es fijo. Por tanto, la complejidad final está determinada únicamente por el tamaño del número primo y es igual a: , donde , son algunas constantes que dependen de cálculos intermedios, en particular, de la elección de la base factorial. $O(c_{1}*2^{(c_{2}+o(1)){\sqrt {logp\;loglogp))})$ $c_{1}$ $c_{2}$

Mejoras

Un algoritmo de cálculo de orden acelerado, cuya esencia es usar una tabla de índice.

Dificultad

La complejidad computacional se reduce a , en comparación con el algoritmo original. $O(2log_{2}(p))$

Algoritmo de cálculo de pedidos

Historia

Enunciado del problema del logaritmo discreto

Algoritmo

Ejemplo

Dificultad

Mejoras

Dificultad

Véase también

Enlaces