exponenciación modular

La exponenciación modular es una exponenciación realizada sobre un módulo . Es útil en informática , especialmente en el campo de la criptografía de clave pública , donde se utiliza tanto en el intercambio de claves Diffie-Hellman como en las claves públicas/privadas RSA .

La exponenciación modular es el resto $c$ cuando un entero $b$ (la base) se eleva a la potencia $e$ (el exponente) y se divide por un entero positivo $m$ (el módulo); es decir, $c = b e mod m$ . De la definición de división, se deduce que $0 \leq c < m$ .

Por ejemplo, dados $b = 5$ , $e = 3$ y $m = 13$ , al dividir $53 = 125$ entre $13$ queda un resto de $c = 8$ .

Cuando $b$ y $m$ son primos relativos , también se puede permitir que el exponente $e$ sea negativo hallando el inverso multiplicativo $d$ de $b$ módulo $m$ (por ejemplo, utilizando el algoritmo euclidiano extendido ). Más precisamente:

c = b e mod m = d - e mod m

, donde

e < 0

y

b \cdot d \equiv 1 (mod m)

.

La exponenciación modular es eficiente para el cálculo, incluso para enteros muy grandes. Por otro lado, se cree que calcular el logaritmo discreto modular —es decir, hallar el exponente $e$ dados $b$ , $c$ y $m—$ es difícil. Este comportamiento unidireccional de la función convierte a la exponenciación modular en una candidata para su uso en algoritmos criptográficos.

Método directo

El método más directo para calcular un exponente modular es calcular directamente $b e$ y luego tomar este número módulo $m$ . Consideremos el intento de calcular $c$ , dados $b = 4$ , $e = 13$ y $m = 497$ :

c \equiv 4 13 (mod 497)

Se podría usar una calculadora para calcular 4 ¹³ ; esto da como resultado 67,108,864. Tomando este valor módulo 497, la respuesta $c$ se determina que es 445.

Tenga en cuenta que $b$ tiene solo un dígito de longitud y que $e$ tiene solo dos dígitos de longitud, pero el valor $b e$ tiene ocho dígitos de longitud.

En criptografía robusta, $b$ suele ser de al menos 1024 bits . ^{[ 1 ]} Consideremos $b = 5 \times 10 76$ y $e = 17$ , ambos valores perfectamente razonables. En este ejemplo, $b$ tiene 77 dígitos y $e$ dos dígitos, pero el valor $b e$ tiene 1304 dígitos decimales. Estos cálculos son posibles en ordenadores modernos, pero la magnitud de estos números reduce considerablemente la velocidad de cálculo. A medida que $b$ y $e$ aumentan aún más para proporcionar mayor seguridad, el valor $b e$ se vuelve inmanejable.

El tiempo necesario para realizar la exponenciación depende del entorno operativo y del procesador. El método descrito anteriormente requiere $Θ (e)$ multiplicaciones para completarse.

Método eficiente en memoria

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, lo que ahorra tiempo (así como memoria) en general.

Este algoritmo utiliza la identidad

(a \cdot b) mod m = [(a mod m) \cdot (b mod m)] mod m

El algoritmo modificado es:

Entradas: Un número entero $b$ (base), un número entero $e$ (exponente) y un número entero positivo $m$ (módulo).

Salidas El exponente modular $c$ donde

c = b e mod m

Inicializa $c = 1$ y la variable de bucle $e' = 0.$
Mientras e′ < e hacer
1. Incrementar $e'$ en 1
2. Calcula $c = (b \cdot c) mod m$
Salida $c$

Nótese que al final de cada iteración del bucle, la ecuación $c \equiv b e' (mod m)$ se cumple. El algoritmo termina cuando el bucle se ha ejecutado $e$ veces. En ese momento, $c$ contiene el resultado de $b e mod m$ .

En resumen, este algoritmo incrementa $e'$ en uno hasta que sea igual a $e$ . En cada paso, multiplica el resultado de la iteración anterior, $c$ , por $b$ y realiza una operación de módulo sobre el producto resultante, manteniendo así el resultado $c$ como un número entero pequeño.

Se presenta nuevamente el ejemplo $b = 4$ , $e = 13$ y $m = 497.$ El algoritmo realiza la iteración trece veces:

(e' = 1) c = (4 \cdot 1) mod 497 = 4 mod 497 = 4

(e' = 2) c = (4 \cdot 4) mod 497 = 16 mod 497 = 16

(e' = 3) c = (4 \cdot 16) mod 497 = 64 mod 497 = 64

(e' = 4) c = (4 \cdot 64) mod 497 = 256 mod 497 = 256

(e' = 5) c = (4 \cdot 256) mod 497 = 1024 mod 497 = 30

(e' = 6) c = (4 \cdot 30) mod 497 = 120 mod 497 = 120

(e' = 7) c = (4 \cdot 120) mod 497 = 480 mod 497 = 480

(e' = 8) c = (4 \cdot 480) mod 497 = 1920 mod 497 = 429

(e' = 9) c = (4 \cdot 429) mod 497 = 1716 mod 497 = 225

(e' = 10) c = (4 \cdot 225) mod 497 = 900 mod 497 = 403

(e' = 11) c = (4 \cdot 403) mod 497 = 1612 mod 497 = 121

(e' = 12) c = (4 \cdot 121) mod 497 = 484 mod 497 = 484

(e' = 13) c = (4 \cdot 484) mod 497 = 1936 mod 497 = 445

Por lo tanto, la respuesta final para $c$ es 445, como en el método directo .

Al igual que el primer método, este requiere $O(e)$ multiplicaciones para completarse. Sin embargo, dado que los números utilizados en estos cálculos son mucho menores que los utilizados 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, exponente, módulo) es si módulo = 1 entonces devuelve 0. c := 1 para e_prime = 0 hasta exponente-1 hacer c := (c * base) mod módulo devolver c

Método binario de derecha a izquierda

Un tercer método reduce drásticamente el número de operaciones necesarias para realizar la exponenciación modular, manteniendo el mismo consumo de memoria que el método anterior. Se trata de una combinación del método anterior y un principio más general denominado exponenciación por elevación al cuadrado (también conocida como exponenciación binaria ).

En primer lugar, es necesario convertir el exponente e $a$ notación binaria . Es decir, $e$ se puede escribir como:

e=\sum _{i=0}^{n-1}a_{i}2^{i}

En dicha notación, la longitud de $e$ es $de n$ bits. $a i$ puede tomar el valor 0 o 1 para cualquier $i$ tal que $0 \leq i < n$ . Por definición, $a n - 1 = 1$ .

El valor $b e$ se puede escribir entonces como:

b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}b^{a_{i}2^{i}}

Por lo tanto, la solución $c$ es:

c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}

Pseudocódigo

El siguiente es un ejemplo en pseudocódigo basado en Applied Cryptography de Bruce Schneier . ^{[ 2 ]} Las entradas base , exponente y módulo corresponden a $b$ , $e$ y $m$ en las ecuaciones dadas anteriormente.

La función modular_pow(base, exponente, módulo) es si módulo = 1 entonces devuelve 0. Afirmar  :: (módulo - 1) * (módulo - 1) no produce desbordamiento de base. resultado := 1 base := base mod módulo mientras exponente > 0 hacer si (exponente mod 2 == 1) entonces resultado := (resultado * base) mod módulo exponente := exponente >> 1 base := (base * base) mod módulo devolver resultado

Nótese que al entrar en el bucle por primera vez, la variable de código base es equivalente a $b$ . Sin embargo, la elevación al cuadrado repetida en la tercera línea de código garantiza que al finalizar cada iteración del bucle, la variable base sea equivalente a $b²i mod m$ , donde $i$ es el número de veces que se ha iterado el bucle. (Esto hace que $i$ $sea$ el siguiente bit operativo del exponente binario exponente , donde el bit menos significativo es $el$ exponente ₀ ).

La primera línea de código simplemente realiza la multiplicación en . Si $a$ es cero, no se ejecuta ningún código ya que esto efectivamente multiplica el total acumulado por uno. Si $a$ es uno, la variable base (que contiene el valor $b$ $2$ $i$ $mod$ $m$ de la base original) simplemente se multiplica en . $\prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}$

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 bucle se ejecuta cuatro veces, con los valores $a 0 = 1, a 1 = 0, a 2 = 1$ y $a 3 = 1$ .

Primero, inicializa el resultado a 1 y conserva el valor de $b$ en la variable $x$ : $R$

R\leftarrow 1\,(=b^{0}){\text{ y }}x\leftarrow b

.

Paso 1) El bit 1 es 1, por lo tanto, se establece ;

R\leftarrow R\cdot x{\text{ }}(=b^{1})

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{2})

Paso 2) El bit 2 es 0, por lo que no se debe reiniciar

R

;

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{4})

Paso 3) El bit 3 es 1, por lo que se establece ;

R\leftarrow R\cdot x{\text{ }}(=b^{5})

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{8})

Paso 4) El bit 4 es 1, por lo que se establece ;

R\leftarrow R\cdot x{\text{ }}(=b^{13})

Este es el último paso, así que no necesitamos elevar

x

al cuadrado .

Hemos terminado: $R$ ya está listo . $b^{13}$

Aquí está el cálculo anterior, donde calculamos $b = 4 elevado$ a la potencia $e = 13$ , realizado módulo 497.

Inicializar:

R\leftarrow 1\,(=b^{0})

y .

x\leftarrow b=4

Paso 1) El bit 1 es 1, por lo tanto, se establece ;

R\leftarrow R\cdot 4\equiv 4{\pmod {497}}

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}

Paso 2) El bit 2 es 0, por lo que no se debe reiniciar

R

;

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}

Paso 3) El bit 3 es 1, por lo que se establece ;

R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}

colocar .

x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}

Paso 4) El bit 4 es 1, por lo que se establece ;

R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}

Hemos terminado: $R$ ahora es , el mismo resultado obtenido en los algoritmos anteriores. $4^{13}\equiv 445{\pmod {497}}$

El tiempo de ejecución de este algoritmo es $O(log$ exponente $)$ . Al trabajar con valores grandes del exponente , esto ofrece una ventaja de velocidad sustancial con respecto a los dos algoritmos anteriores, cuyo tiempo es $O($ exponente $)$ . Por ejemplo, si el exponente fuera ^2²⁰ = 1048576, este algoritmo tendría 20 pasos en lugar de 1048576.

Implementación en Lua

función modPow(b, e, m) si m == 1 entonces devolver 0 fin local r = 1 b = b % m mientras e > 0 hacer si e % 2 == 1 entonces r = (r*b) % m fin b = (b*b) % m e = e >> 1 --use 'e = math.floor(e / 2)' en Lua 5.2 o versiones anteriores fin devolver r 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 la multiplicación $(mod m)$ antes de continuar. Para simplificar, aquí se omite el cálculo del módulo. Este ejemplo muestra cómo calcular usando la exponenciación binaria de izquierda a derecha. El exponente es 1101 en binario; hay cuatro bits, por lo que hay cuatro iteraciones. $b^{13}$

Inicializa el resultado a 1: . $r\leftarrow 1\,(=b^{0})$

Paso 1) ; bit 1 = 1, por lo tanto, calcular ;

r\leftarrow r^{2}\,(=b^{0})

r\leftarrow r\cdot b\,(=b^{1})

Paso 2) ; bit 2 = 1, por lo tanto, calcular ;

r\leftarrow r^{2}\,(=b^{2})

r\leftarrow r\cdot b\,(=b^{3})

Paso 3) ; bit 3 = 0, por lo que hemos terminado con este paso;

r\leftarrow r^{2}\,(=b^{6})

Paso 4) ; bit 4 = 1, por lo tanto, calcular .

r\leftarrow r^{2}\,(=b^{12})

r\leftarrow r\cdot b\,(=b^{13})

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 proporciona el número mínimo posible de multiplicaciones. El contraejemplo más pequeño se da para una potencia de 15, donde el método binario requiere seis multiplicaciones. En cambio, se puede formar ^x³^con^{dos multiplicaciones, luego x⁶ elevando x³ al cuadrado, después x¹² elevando x⁶ al cuadrado y, finalmente, x¹⁵}multiplicando x¹² y x³ , ^logrando así el resultado deseado ^con^solo cinco ^{multiplicaciones}. Sin embargo , a ^{continuación} se describen en varias páginas cómo se podrían idear 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 $los k$ términos anteriores, se puede calcular eficientemente módulo $n$ mediante el cálculo $de A m mod n$ , donde $A$ es la matriz complementaria $k \times k$ correspondiente . Los métodos anteriores se adaptan fácilmente a esta aplicación. Esto se puede utilizar , por ejemplo, para realizar pruebas de primalidad de números grandes $n .$

Pseudocódigo

Un algoritmo recursivo para ModExp(A, b, c)= $A b mod c$ , donde $A$ es una matriz cuadrada.

La función Matrix_ModExp(Matrix A, int b, int c) es: si b == 0, entonces devuelve I. // La matriz identidad. Si (b mod 2 == 1) , entonces devuelve (A * Matrix_ModExp(A, b - 1, c)) mod c. Matriz D := Matrix_ModExp(A, b / 2, c) devolver (D * D) mod c

Grupos cíclicos finitos

El intercambio de claves Diffie-Hellman utiliza la 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 matrices modulares $C \equiv AB (mod n)$ se reemplaza simplemente en todas partes por la multiplicación de grupos $c = ab$ .

Exponenciación modular reversible y cuántica

En computación cuántica , la exponenciación modular se presenta como el cuello de botella del algoritmo de Shor , donde debe calcularse mediante un circuito compuesto por compuertas reversibles , las cuales pueden dividirse aún más en compuertas 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 la exponenciación en cada llamada, lo que permite diversas optimizaciones del circuito. ^{[ 3 ]}

Implementaciones de software

Dado que la exponenciación modular es una operación importante en la informática, y existen algoritmos eficientes (véase más arriba) que son mucho más rápidos que simplemente elevar a la potencia 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 integrada de Pythonpow() (exponenciación) [1] toma un tercer argumento opcional, el módulo.
La clase de .NET FrameworkBigInteger tiene un ModPow()método para realizar exponenciación modular.
La clase de Javajava.math.BigInteger tiene un modPow()método para realizar la exponenciación modular.
Función de MATLABpowermod del cuadro de herramientas de matemáticas simbólicas
Wolfram Language tiene la función PowerMod.
El módulo de PerlMath::BigInt tiene un bmodpow()método [2] para realizar la exponenciación modular.
Raku tiene una rutina incorporada expmod.
El tipo de Gobig.Int contiene un Exp()método (de exponenciación) [3] cuyo tercer parámetro, si no es nulo, es el módulo.
La biblioteca BC Math de PHPbcpowmod() tiene una 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 paquete de Rubyopenssl tiene el OpenSSL::BN#mod_expmétodo [6] para realizar la exponenciación modular.

Véase 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

^ "Weak Diffie–Hellman and the Logjam Attack" . weakdh.org . Consultado el 3 de mayo de 2019 .
^ Schneier 1996 , pág. 244.
^ IL Markov, M. Saeedi (2012). "Circuitos cuánticos optimizados con constantes para la multiplicación modular y la exponenciación". Información cuántica y computación . 12 ( 5– 6): 0361– 0394. arXiv : 1202.6614 . Bibcode : 2012arXiv1202.6614M . doi : 10.26421/QIC12.5-6-1 . S2CID 16595181 .

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, Applet Java de exponenciación modular rápida
Gordon, Daniel M. (1998). "Un estudio de métodos de exponenciación rápida" (PDF) . Journal of Algorithms . 27 (1). Elsevier BV: 129– 146. doi : 10.1006/jagm.1997.0913 . ISSN 0196-6774 .

[1] "Weak Diffie–Hellman and the Logjam Attack" . weakdh.org . Consultado el 3 de mayo de 2019 .

[schneier96p244-2] Schneier 1996 , pág. 244.

[3] IL Markov, M. Saeedi (2012). "Circuitos cuánticos optimizados con constantes para la multiplicación modular y la exponenciación". Información cuántica y computación . 12 ( 5– 6): 0361– 0394. arXiv : 1202.6614 . Bibcode : 2012arXiv1202.6614M . doi : 10.26421/QIC12.5-6-1 . S2CID 16595181 .

[ 1 ]

[ 2 ]

[ 3 ]