Algoritmo de Gelfond-Shanks

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 28 de diciembre de 2019; las comprobaciones requieren 9 ediciones .

El algoritmo Gelfond-Shanks ( ing. Baby-step paso gigante ; también llamado algoritmo de pasos grandes y pequeños ; también puede encontrar muy a menudo el algoritmo de coincidencia de nombres , por ejemplo, en el libro de Vasilenko "Number-Theoretic Algorithms of Cryptography" ) - en teoría de grupos, un algoritmo determinista de logaritmos discretos en el grupo multiplicativo del anillo de residuos módulo un número primo. Fue propuesto por el matemático soviético Alexander Gelfond en 1962 y Daniel Shanks en 1972 [1] [2] [3] .

El método simplifica teóricamente la solución del problema del logaritmo discreto, sobre cuya complejidad computacional se construyen muchos criptosistemas de clave pública . Se refiere a los métodos de reunión en el medio .

Alcance

El problema del logaritmo discreto es de gran interés para la construcción de criptosistemas de clave pública . En el supuesto de una complejidad computacional extremadamente alta para resolver este problema, dichos algoritmos criptográficos se basan, por ejemplo, en RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin y otros. En ellos, el criptoanalista puede obtener la clave privada tomando el logaritmo discreto de la clave pública (conocido por todos), y usándolo para convertir el texto cifrado en el texto del mensaje. Sin embargo, cuanto más difícil sea encontrarlo (cuantas más operaciones necesites hacer para encontrar el logaritmo discreto), más seguro es el criptosistema. Una forma de aumentar la complejidad del problema del logaritmo discreto es crear un criptosistema basado en un grupo con un orden grande (donde el logaritmo será módulo un número primo grande). En el caso general, tal problema se resuelve mediante enumeración exhaustiva , pero este algoritmo permite en algunos casos simplificar la búsqueda del exponente (reducir el número de pasos) al calcular módulo un número primo, en el caso más favorable, por la raíz cuadrada de veces [4] , pero esta reducción aún no es suficiente para resolver el problema en una computadora electrónica en un tiempo razonable (la cuestión de resolver el problema del logaritmo discreto en tiempo polinomial en una computadora personal aún está abierta) [5] .

Problema de logaritmos discretos

Sea dado un grupo cíclico con generador que contenga elementos. Un número entero (en el rango de a ) se denomina logaritmo en base discreta de un elemento si la relación es verdadera: $GRAMO$ $gramo$ $norte$ $X$ ${\ estilo de visualización 0}$ $n-1$ $Hing$ $gramo$

{\ estilo de visualización g ^ {x} = h.}

La tarea del logaritmo discreto es determinar para dado . $h$ $gramo$ $X$

Formalmente, el problema del logaritmo discreto se plantea de la siguiente manera [6] :

{\begin{cases}{\text{Entrada:}}\quad &g,h,n\in \mathbb {N} \\{\text{Salida:}}\quad &x\in \mathbb {N } :\ g^{x}\equiv h{\pmod {n}}\\\end{casos}}

siempre que no exista, y también puede ser un número primo o un número compuesto. $X$ $norte$

Teoría

La idea del algoritmo es elegir la relación óptima de tiempo y memoria , es decir, en una búsqueda mejorada del exponente.

Sean dados un grupo de orden cíclico , un generador del grupo y algún elemento del grupo . La tarea se reduce a encontrar un número entero para el cual $GRAMO$ $norte$ $\alfa$ $\beta$ $X$

\alpha^x = \beta\,.

El algoritmo de Gelfond-Shanks se basa en la representación en la forma , donde , y enumeración de y . La restricción de y se deriva del hecho de que el orden del grupo no excede , lo que significa que los rangos indicados son suficientes para obtener todos los posibles del medio intervalo . Esta representación es equivalente a la igualdad $X$ $x=i\cdot mj$ $m = \left\lpiso \sqrt{n} \right\rpiso + 1$ $1 \leq i \leq m$ $0 \ leq j < m$ $i$ $j$ $metro$ $X$ $\izquierda[0; m\derecha)$

$\alpha^{im} = \beta \alpha^j\,.$

(una)

El algoritmo realiza cálculos previos para diferentes valores y los almacena en una estructura de datos que permite una búsqueda eficiente, y luego itera sobre todos los valores posibles y verifica si coincide con algún valor . Así, se encuentran índices y que satisfacen la relación (1) y nos permiten calcular el valor [7] . $\alpha^{im}$ $i$ $j$ ${\ estilo de visualización \ beta \ alfa ^ {j))$ $i$ $i$ $j$ $x=i\cdot mj$

Algoritmo

Entrada : Un grupo de orden cíclico , un generador y algún elemento . $GRAMO$ $norte$ $\alfa$ $\beta$

Salida : Un número que satisface . $X$ $\alpha^{x}=\beta$

$metro$ ← $\left\lpiso {\sqrt {n}}\right\rpiso +1$
Calcular ← . $\gama$ ${\ estilo de visualización \ alfa ^ {m}}$
Para cualquier lugar ≤ ≤ : $i$ $una$ $i$ $metro$
1. Escriba en la tabla ( , ). (Ver la sección de Implementación) $i$ $\gama$
2. $\gama$ ← • $\gama$ ${\ estilo de visualización \ alfa ^ {m}}$
Para cualquier lugar ≤ ≤ : $j$ ${\ estilo de visualización 0}$ $j$ $m-1$
1. Calcula _ ${\ estilo de visualización \ beta \ alfa ^ {j))$
2. Compruebe si la tabla contiene. ${\ estilo de visualización \ beta \ alfa ^ {j))$
3. En caso afirmativo, devuelva - . ${\ estilo de visualización soy}$ $j$
4. Si no, continúa con el bucle [1] [2] [7] .

Justificación del algoritmo

Es necesario probar que necesariamente existen los mismos elementos en las tablas, es decir, existen tales y , que . Esta igualdad tiene lugar en el caso de , o . Porque , la desigualdad se cumple . Para pares diferentes y tenemos , ya que de lo contrario resultaría que con la elección indicada sólo es posible en el caso de , y, por tanto, . Así, las expresiones toman todos los valores en el rango de a , que, debido a que contiene todos los valores posibles de a . Por lo tanto, para algunos y se cumple la igualdad [2] . $i$ $j$ ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j))$ $mi=x+j{\pmod {n}}$ $x=mi-j{\pmod {n))$ ${\ estilo de visualización 1 \ leq i \ leq m}$ ${\ estilo de visualización 1 \ leq j \ leq m}$ $0\leq mi-j\leq m^{2}-1$ ${\ estilo de visualización (i_ {1}, j_ {1})}$ ${\ estilo de visualización (i_ {2}, j_ {2})}$ $mi_{1}-j_{1}\neq mi_{2}-j_{2}$ $m(i_{1}-i_{2})=(j_{1}-j_{2})$ ${\ estilo de visualización i_ {1}, i_ {2}}$ $i_{1}=i_{2}$ ${\ estilo de visualización j_{1}=j_{2))$ ${\ Displaystyle mi-j}$ ${\ estilo de visualización 0}$ ${\ estilo de visualización m^{2}-1}$ ${\ estilo de visualización m ^ {2}> n}$ $X$ ${\ estilo de visualización 0}$ $n-1$ $i$ $j$ $x=mi-j{\pmod {n))$

Estimación de la complejidad de un algoritmo

Supongamos que necesitamos resolver , donde y son números enteros positivos menores que . Una forma es iterar secuencialmente desde hasta , comparando el valor con . En el peor de los casos, necesitamos pasos (cuando ). En promedio tomará pasos. De lo contrario, podemos representar como . Así, el problema se reduce a encontrar y . En este caso, puede reescribir la tarea como o . Ahora podemos iterar sobre todos los valores posibles en el lado derecho de la expresión. En este caso, estos son todos los números desde hasta . Estos son los llamados grandes pasos. Se sabe que uno de los valores obtenidos para es el requerido. Podemos registrar todos los valores del lado derecho de la expresión en una tabla. Luego podemos calcular los valores posibles para el lado izquierdo para diferentes valores de . Estos son todos los números desde uno de los cuales es el deseado, y junto con el valor correcto del lado derecho da el resultado deseado para . Así, la tarea se reduce a ordenar los distintos valores del lado izquierdo y buscarlos en la tabla. Si el valor deseado se encuentra en la tabla, entonces hemos encontrado y, por lo tanto, el correspondiente . Esta ilustración demuestra la velocidad del algoritmo. En promedio, las operaciones se realizan. En el peor de los casos, se requieren operaciones [3] . $h = ng$ $h$ $gramo$ $100$ $norte$ $una$ $100$ $n \ c punto g$ $h$ $100$ $n=99$ $cincuenta$ $norte$ $n=10a-b$ $a$ $b$ $h=(10a-b)g$ $h+bg=10ag$ $a$ $una$ $diez$ $a$ $b$ ${\ estilo de visualización 0}$ $9$ $norte$ $b$ $n=10a+b$ ${\ estilo de visualización 1,5 {\ sqrt {n}}}$ ${\ estilo de visualización 2 {\ sqrt {n}}}$

Ejemplo

A continuación se muestra un ejemplo de cómo resolver el problema del logaritmo discreto con un orden de grupo pequeño. En la práctica, los criptosistemas utilizan grupos de orden superior para mejorar la fuerza criptográfica .

Que se sepa . Al principio, crearemos y completaremos la tabla para los "grandes pasos". Elijamos ← ( ). Luego se ejecutará de a . $5^{x}\equiv 3{\pmod {23}}$ $metro=5$ ${\ estilo de visualización {\ sqrt {16}} +1}$ $i$ $una$ $5$

$i$	una	2	3	cuatro	5
${\ estilo de visualización 5 ^ {im} = 20 ^ {i}}$	veinte	9	19	12	diez

Encontremos un valor adecuado para que los valores de ambas tablas coincidan $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	una	2	3	cuatro
${\ estilo de visualización \ beta \ alfa ^ {j} = 3}$ · ${\ estilo de visualización 5^{j}}$	quince	6	7	12

Se puede ver que en la segunda tabla para , dicho valor ya está en la primera tabla. Encuentre [2] . ${\ estilo de visualización j = 4}$ $x=mi-j=5\cdot 4-4=16$

Implementación

Hay una forma de mejorar el rendimiento del algoritmo de Gelfond-Shanks. Consiste en utilizar un esquema eficiente de acceso a tablas. La mejor manera es usar una tabla hash . Debe hacer hash en el segundo componente y luego realizar una búsqueda de hash en la tabla en el bucle principal en . Dado que acceder y agregar elementos a una tabla hash lleva tiempo ( una constante ), esto asintóticamente no ralentiza el algoritmo. $\gama$ $O(1)$

El tiempo de ejecución del algoritmo se estima como , que es mucho mejor que el tiempo de ejecución de la enumeración exhaustiva de exponentes [4] . $O({\raíz cuadrada {n)))$ $En)$

Características

El algoritmo de Gelfond-Shanks funciona para un grupo cíclico finito arbitrario [7] [3] .
No es necesario saber el orden del grupo de antemano. El algoritmo también funciona si es el límite superior del orden del grupo [7] . $GRAMO$ $norte$
Normalmente, el algoritmo de Gelfond-Shanks se usa para grupos cuyo orden es un número primo . Si el orden es un número compuesto , entonces se recomienda el uso del algoritmo de Polig-Hellman [7] .
El algoritmo de Gelfond-Shanks requiere memoria. Es posible elegir uno más pequeño en el primer paso del algoritmo. Esto aumenta el tiempo de ejecución del programa a . También es posible usar el método ρ de Pollard para logaritmos discretos , que funciona al mismo tiempo, pero requiere una pequeña cantidad de memoria [7] . $En)$ $metro$ ${\ estilo de visualización O (n/m)}$

Notas

↑ 1 2 D. Mangos. La infraestructura de un campo cuadrático real y sus aplicaciones. Actas de la Conferencia de Teoría de Números. - Universidad de Colorado, Boulder, 1972. - S. pp. 217-224. .
↑ 1 2 3 4 IA Pankratova. Métodos teóricos de números en criptografía: libro de texto. - Tomsk: TSU, 2009. - S. 90-98. — 120 s. .
↑ 1 2 3 VI Nechaev. Elementos de criptografía. Fundamentos de la Teoría de la Seguridad de la Información . - M. : Escuela Superior, 1999. - S. 61 -67. — 109 pág. — ISBN 5-06-003644-8 . .
↑ 12 DC Terr . Una modificación del algoritmo de paso de gigante paso de bebé de Shanks . — Matemáticas de la Computación. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Algoritmos teóricos de números en criptografía . - Moscú: MTSNMO , 2003. - S. 163-185. — 328 pág. — ISBN 5-94057-103-4 . Copia archivada (enlace no disponible) . Fecha de acceso: 23 de noviembre de 2016. Archivado desde el original el 27 de enero de 2007. (indefinido) .
↑ Yan, Song Y. Pruebas de primalidad y factorización de enteros en criptografía de clave pública . - 2. - Springer, 2009. - S. 257-260. — 374 pág. — ISBN 978-0-387-77267-7 . .
↑ 1 2 3 4 5 6 Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Introducción a los métodos criptográficos de teoría numérica. - 1ª ed.- San Petersburgo. : Lan, 2010. - S. 279-298. — 400 s. Con. - ISBN 978-5-8114-1116-0 . .

Literatura

A.O. Gelfond, Yu.V. Linnik. Métodos elementales en teoría analítica de números. - M. : Fizmatgiz, 1962. - 272 p.

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin