Un apunte sobre el cálculo de la inversa modular para criptografía
Autores: Bufalo, Michele; Bufalo, Daniele; Orlando, Giuseppe
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Un apunte sobre el cálculo de la inversa modular para criptografía
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Algoritmos criptográficos
Operación módulo
Inversos multiplicativos
Enteros positivos
Costo computacional
Solución explícita
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
En la literatura, hay varios algoritmos criptográficos (RSA, ElGamal, NTRU, etc.) que requieren múltiples cálculos de inversos multiplicativos módulo. En este documento, describimos la operación módulo y recordamos los enfoques principales para calcular el módulo. Luego, dados enteros positivos, presentamos la secuencia , donde , y . Respecto a la secuencia anterior, mostramos que está acotada y admite una solución explícita, periódica y simple. El resultado principal es que el inverso de módulo se da con . El costo computacional de dicho índice es , que es menor que la función phi de Euler. Además, sugerimos un algoritmo para el cálculo de usando multiplicaciones simples en lugar de multiplicaciones modulares. Este último tiene una complejidad versus complejidad (algoritmo ingenuo) o complejidad (algoritmo extendido de Euclides). Por lo tanto, el procedimiento anterior es más conveniente cuando (por ejemplo, ).
Descripción
En la literatura, hay varios algoritmos criptográficos (RSA, ElGamal, NTRU, etc.) que requieren múltiples cálculos de inversos multiplicativos módulo. En este documento, describimos la operación módulo y recordamos los enfoques principales para calcular el módulo. Luego, dados enteros positivos, presentamos la secuencia , donde , y . Respecto a la secuencia anterior, mostramos que está acotada y admite una solución explícita, periódica y simple. El resultado principal es que el inverso de módulo se da con . El costo computacional de dicho índice es , que es menor que la función phi de Euler. Además, sugerimos un algoritmo para el cálculo de usando multiplicaciones simples en lugar de multiplicaciones modulares. Este último tiene una complejidad versus complejidad (algoritmo ingenuo) o complejidad (algoritmo extendido de Euclides). Por lo tanto, el procedimiento anterior es más conveniente cuando (por ejemplo, ).