La exponenciación modular es un tipo de exponenciación que se realiza sobre un módulo . Es útil en informática , especialmente en el campo de la criptografía de clave pública .
La operación de exponenciación modular calcula el resto cuando un entero b (la base) elevado a la e- ésima potencia (el exponente), b e , se divide por un entero positivo m (el módulo). En símbolos, dada la base b , el exponente e y el módulo m , la exponenciación modular c es: c = b e mod m . De la definición de c , se deduce que 0 ≤ c < m .
Por ejemplo, dado b = 5 , e = 3 y m = 13 , la solución c = 8 es el resto de dividir 5 3 = 125 entre 13 .
La exponenciación modular se puede realizar con un exponente negativo e encontrando el inverso multiplicativo modular d de b módulo m usando el algoritmo euclidiano extendido . Es decir:
- c = b e mod m = d - e mod m , donde e <0 y b ⋅ d ≡ 1 (mod m ) .
La exponenciación modular similar a la descrita anteriormente se considera fácil de calcular, incluso cuando los números enteros involucrados son enormes. Por otro lado, se cree que es difícil calcular el logaritmo discreto modular , es decir, la tarea de encontrar el exponente e cuando se dan b , c y m . Este comportamiento de función unidireccional hace que la exponenciación modular sea un candidato para su uso en algoritmos criptográficos.
Método directo
El método más directo para calcular un exponente modular es calcular b e directamente y luego tomar este número módulo m . Considere intentar calcular c , dado b = 4 , e = 13 y m = 497 :
- c ≡ 4 13 (mod 497)
Se podría usar una calculadora para calcular 4 13 ; esto asciende a 67,108,864. Tomando este valor módulo 497, se determina que la respuesta c es 445.
Tenga en cuenta que b tiene solo un dígito y que e solo tiene dos dígitos, pero el valor b e tiene 8 dígitos.
En criptografía fuerte, b suele tener al menos 1024 bits . [1] Considere b = 5 × 10 76 y e = 17 , ambos de los cuales son perfectamente valores razonables. En este ejemplo, b tiene una longitud de 77 dígitos ye tiene una longitud de 2 dígitos, pero el valor b e tiene una longitud de 1.304 dígitos decimales. Tales cálculos son posibles en las computadoras modernas, pero la magnitud de tales números hace que la velocidad de los cálculos disminuya considerablemente. Como b y e incremento aún más para proporcionar una mayor seguridad, el valor b e se convierte en difícil de manejar.
El tiempo necesario para realizar la potenciación depende del entorno operativo y del procesador. El método descrito anteriormente requiere multiplicaciones O ( e ) para completar.
Método de memoria eficiente
Mantener los números más pequeños requiere operaciones de reducción modular adicionales, pero el tamaño reducido hace que cada operación sea más rápida, ahorrando tiempo (así como memoria) en general.
Este algoritmo hace uso de la identidad
- ( a ⋅ b ) mode m = [( a mode m ) ⋅ ( b mode m )] mode m
El algoritmo modificado es:
- Establezca c = 1 , e ′ = 0 .
- Incrementar e ′ en 1.
- Establezca c = (b ⋅ c) mod m .
- Si e ′ < e , vaya al paso 2. De lo contrario, c contiene la solución correcta de c ≡ b e (mod m ) .
Tenga en cuenta que en cada paso por el paso 3, la ecuación c ≡ b e ′ (mod m ) se cumple. Cuando el paso 3 se ha ejecutado e veces, entonces c contiene la respuesta que se buscaba. En resumen, este algoritmo básicamente cuenta e ′ de uno en uno hasta que e ′ llega a e , haciendo una operación de multiplicar por by una operación de módulo cada vez que agrega uno (para asegurar que los resultados permanezcan pequeños).
El ejemplo b = 4 , e = 13 y m = 497 se presenta nuevamente. El algoritmo pasa por el paso 3 trece veces:
- e ′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4 .
- e ′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16 .
- e ′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64 .
- e ′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256 .
- e ′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30 .
- e ′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120 .
- e ′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480 .
- e ′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429 .
- e ′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225 .
- e ′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403 .
- e ′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121 .
- e ′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484 .
- e ′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445 .
Por tanto, la respuesta final para c es 445, como en el primer método.
Como el primer método, esto requiere multiplicaciones O ( e ) para completar. Sin embargo, dado que los números usados en estos cálculos son mucho más pequeños que los números usados en los cálculos del primer algoritmo, el tiempo de cálculo disminuye en un factor de al menos O ( e ) en este método.
En pseudocódigo, este método se puede realizar de la siguiente manera:
la función modular_pow (base, exponent, modulus) es si modulus = 1 entonces devuelve 0 c: = 1 para e_prime = 0 a exponente-1 hacer c: = (c * base) mod módulo de retorno c
Método binario de derecha a izquierda
Un tercer método reduce drásticamente el número de operaciones para realizar exponenciación modular, mientras mantiene la misma huella de memoria que en el método anterior. Es una combinación del método anterior y un principio más general llamado exponenciación al cuadrado (también conocido como exponenciación binaria ).
Primero, se requiere que el exponente e se convierta a notación binaria . Es decir, e se puede escribir como:
En tal notación, la longitud de e es n bits. a i puede tomar el valor 0 o 1 para cualquier i tal que 0 ≤ i < n . Por definición, a n - 1 = 1 .
El valor b e se puede escribir como:
Por tanto, la solución c es:
Pseudocódigo
El siguiente es un ejemplo en pseudocódigo basado en la criptografía aplicada de Bruce Schneier . [2] Las entradas de base , exponente , y módulo corresponden a b , e , y m en las ecuaciones dadas arriba.
función modular_pow (base, exponent, modulus) es si módulo = 1 luego devuelve 0 Assert :: (modulus - 1) * (modulus - 1) no desborda la base resultado: = 1 Base: = base mod módulo mientras exponente> 0 hacer si (exponente mod 2 == 1) a continuación, dar lugar a: = (resultado * base) mod módulo exponente: = exponente >> 1 Base: = (base * base) mod módulo de retorno resultado
Tenga en cuenta que al ingresar al bucle por primera vez, la base de la variable de código es equivalente a b . Sin embargo, el cuadrado repetido en la tercera línea de código asegura que al completar cada ciclo, la base de la variable sea equivalente a b 2 i mod m , donde i es el número de veces que se ha iterado el ciclo. (Esto hace que i sea el siguiente bit de trabajo del exponente del exponente binario , donde el bit menos significativo es el exponente 0 ).
La primera línea de código simplemente realiza la multiplicación en . Si unes cero, no se ejecuta ningún código, ya que esto multiplica efectivamente el total acumulado por uno. Si unen su lugar es uno, la base de la variable (que contiene el valor b 2 i mod m de la base original) simplemente se multiplica.
En este ejemplo, la base b se eleva al exponente e = 13 . El exponente es 1101 en binario. Hay cuatro dígitos binarios, por lo que el ciclo se ejecuta cuatro veces, con valores a 0 = 1, a 1 = 0, a 2 = 1 y a 3 = 1 .
Primero, inicializa el resultado a 1 y conservar el valor de b en la variable x :
- .
- Paso 1) el bit 1 es 1, así que establezca ;
- colocar .
- Paso 2) el bit 2 es 0, así que no reinicie R ;
- colocar .
- Paso 3) el bit 3 es 1, así que establezca ;
- colocar .
- Paso 4) el bit 4 es 1, así que establezca ;
- Este es el último paso, por lo que no es necesario elevar al cuadrado x .
Hemos terminado: R es ahora.
Aquí está el cálculo anterior, donde calculamos b = 4 a la potencia e = 13 , realizado en módulo 497.
Inicializar:
- y .
- Paso 1) el bit 1 es 1, así que establezca ;
- colocar .
- Paso 2) el bit 2 es 0, así que no reinicie R ;
- colocar .
- Paso 3) el bit 3 es 1, así que establezca ;
- colocar .
- Paso 4) el bit 4 es 1, así que establezca ;
Hemos terminado: R es ahora, el mismo resultado obtenido en los algoritmos anteriores.
El tiempo de ejecución de este algoritmo es O ( exponente logarítmico ) . Cuando se trabaja con valores grandes de exponente , esto ofrece un beneficio de velocidad sustancial sobre los dos algoritmos anteriores, cuyo tiempo es O ( exponente ) . Por ejemplo, si el exponente fuera 2 20 = 1048576, este algoritmo tendría 20 pasos en lugar de 1048576 pasos.
Implementación en Lua
función modPow (b, e, m) si m == 1 entonces devuelve 0 en caso contrario local r = 1 b = b% m mientras que e> 0 hacer si e% 2 == 1 a continuación, r = (r * b)% m final e = e >> 1 --use 'e = math.floor (e / 2)' en Lua 5.2 o anterior b = (b ^ 2)% m fin volver r fin fin
Método binario de izquierda a derecha
También podemos usar los bits del exponente en orden de izquierda a derecha. En la práctica, normalmente querríamos el resultado módulo algún módulo m . En ese caso, reduciríamos cada resultado de multiplicación (mod m ) antes de continuar. Por simplicidad, aquí se omite el cálculo del módulo. Este ejemplo muestra cómo calcularusando exponenciación binaria de izquierda a derecha. El exponente es 1101 en binario; hay 4 bits, por lo que hay 4 iteraciones.
Inicialice el resultado a 1: .
- Paso 1) ; bit 1 = 1, así que calcule ;
- Paso 2) ; bit 2 = 1, así que calcule ;
- Paso 3) ; bit 3 = 0, así que hemos terminado con este paso;
- Paso 4) ; bit 4 = 1, así que calcule .
Multiplicaciones mínimas
En El arte de la programación informática , vol. 2, Algoritmos seminuméricos , página 463, Donald Knuth señala que, contrariamente a algunas afirmaciones, este método no siempre da el número mínimo posible de multiplicaciones. El contraejemplo más pequeño es para una potencia de 15, cuando el método binario necesita seis multiplicaciones. En su lugar, forme x 3 en dos multiplicaciones, luego x 6 elevando al cuadrado x 3 , luego x 12 elevando al cuadrado x 6 y finalmente x 15 multiplicando x 12 y x 3 , logrando así el resultado deseado con solo cinco multiplicaciones. Sin embargo, siguen muchas páginas en las que se describe cómo podrían idearse tales secuencias en general.
Generalizaciones
Matrices
El m -ésimo término de cualquier secuencia recursiva constante (como los números de Fibonacci o los números de Perrin ) donde cada término es una función lineal de k términos anteriores se puede calcular de manera eficiente módulo n calculando A m mod n , donde A es el k correspondiente × k matriz complementaria . Los métodos anteriores se adaptan fácilmente a esta aplicación. Esto se puede utilizar para pruebas de primalidad de números grandes n , por ejemplo.
- Pseudocódigo
Un algoritmo recursivo para ModExp(A, b, c)
= A b mod c , donde A es una matriz cuadrada.
function Matrix_ModExp (Matrix A, int b, int c) es si b == 0 luego devuelve I // La matriz de identidad if (b mod 2 == 1) luego devuelve (A * Matrix_ModExp (A, b - 1, c) ) mod c Matriz D: = Matrix_ModExp (A, b / 2, c) volver (D * D) mod c
Grupos cíclicos finitos
El intercambio de claves Diffie-Hellman utiliza exponenciación en grupos cíclicos finitos. Los métodos anteriores para la exponenciación de matrices modulares se extienden claramente a este contexto. La multiplicación de matriz modular C ≡ AB (mod n ) simplemente se reemplaza en todas partes por la multiplicación de grupo c = ab .
Exponenciación modular cuántica y reversible
En la computación cuántica , la exponenciación modular aparece como el cuello de botella del algoritmo de Shor , donde debe ser calculado por un circuito que consta de puertas reversibles , que se pueden dividir en puertas cuánticas apropiadas para un dispositivo físico específico. Además, en el algoritmo de Shor es posible conocer la base y el módulo de exponenciación en cada llamada, lo que permite varias optimizaciones del circuito. [3]
Implementaciones de software
Debido a que la exponenciación modular es una operación importante en la informática, y existen algoritmos eficientes (ver arriba) que son mucho más rápidos que simplemente exponenciar y luego tomar el resto, muchos lenguajes de programación y bibliotecas de enteros de precisión arbitraria tienen una función dedicada para realizar la exponenciación modular :
- La función incorporada de Python
pow()
(exponenciación) [1] toma un tercer argumento opcional, el módulo - La
BigInteger
clase de .NET Framework tiene unModPow()
método para realizar exponenciación modular - La
java.math.BigInteger
clase de Java tiene unmodPow()
método para realizar exponenciación modular - MATLAB 's
powermod
función de Symbolic Math Toolbox - Wolfram Language tiene la función PowerMod
- El
Math::BigInt
módulo de Perl tiene unbmodpow()
método [2] para realizar exponenciación modular - Raku tiene una rutina incorporada
expmod
. - El
big.Int
tipo de Go contiene unExp()
método (exponenciación) [3] cuyo tercer parámetro, si no es nulo, es el módulo - La biblioteca BC Math de PHP tiene una
bcpowmod()
función [4] para realizar exponenciación modular - La biblioteca GNU Multiple Precision Arithmetic Library (GMP) contiene una
mpz_powm()
función [5] para realizar exponenciación modular - Función personalizada
@PowerMod()
para FileMaker Pro (con ejemplo de cifrado RSA de 1024 bits ) - El
openssl
paquete de Ruby tiene elOpenSSL::BN#mod_exp
método [6] para realizar una exponenciación modular. - La calculadora HP Prime tiene la función CAS.powmod () [7] para realizar exponenciación modular. Para a ^ b mod c, a no puede ser mayor que 1 EE 12. Esta es la precisión máxima de la mayoría de las calculadoras HP, incluida la Prime.
Ver también
- Reducción de Montgomery , para calcular el resto cuando el módulo es muy grande.
- Multiplicación de Kochanski , método serializable para calcular el resto cuando el módulo es muy grande
- Reducción de Barrett , algoritmo para calcular el resto cuando el módulo es muy grande.
Referencias
- ^ "Débil Diffie-Hellman y el ataque del atasco" . debildh.org . Consultado el 3 de mayo de 2019 .
- ^ Schneier 1996 , p. 244.
- ^ IL Markov, M. Saeedi (2012). "Circuitos cuánticos optimizados para constantes para multiplicación y exponenciación modular". Computación e información cuántica . 12 (5–6): 0361–0394. arXiv : 1202.6614 . Código bibliográfico : 2012arXiv1202.6614M .
enlaces externos
- Schneier, Bruce (1996). Criptografía aplicada: protocolos, algoritmos y código fuente en C, segunda edición (2ª ed.). Wiley. ISBN 978-0-471-11709-4.
- Paul Garrett, subprograma Java de exponenciación modular rápida
- Gordon, Daniel M. (1998). "Una encuesta de métodos de exponenciación rápida" (PDF) . Revista de algoritmos . Elsevier BV. 27 (1): 129-146. doi : 10.1006 / jagm.1997.0913 . ISSN 0196-6774 .