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 que queda 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, dado $b = 5$ , $e = 3$ y $m = 13$ , al dividir $53 = 125$ por $13$ queda un resto de $c = 8$ .

La exponenciación modular se puede realizar con un exponente negativo $e$ hallando el inverso multiplicativo modular $d$ de $b$ módulo $m$ utilizando el algoritmo euclidiano extendido . Es decir:

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

, donde

e < 0

b \cdot d \equiv 1 (mod m)

La exponenciación modular es eficiente para calcular, incluso para números enteros muy grandes. Por otro lado, se cree que calcular el logaritmo discreto modular (es decir, encontrar el exponente $e$ cuando se dan $b$ , $c$ y $m$ ) es difícil. Este comportamiento de función unidireccional hace que la exponenciación modular sea 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 $b e$ directamente y luego tomar este número módulo $m$ . Consideremos que intentamos calcular $c$ , dados $b = 4$ , $e = 13$ y $m = 497$ :

c \equiv 4 13 (mód 497)

Se puede utilizar una calculadora para calcular 4 ¹³ ; esto da como resultado 67.108.864. Si tomamos este valor módulo 497, se determina que la respuesta $c$ 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 8 dígitos de longitud.

En criptografía fuerte, $b$ es a menudo al menos 1024 bits . ^[1] Considere $b = 5 \times 10 76$ y $e = 17$ , ambos valores perfectamente razonables. En este ejemplo, $b$ tiene 77 dígitos de longitud y $e$ tiene 2 dígitos de longitud, pero el valor $b e$ tiene 1.304 dígitos decimales de longitud. Tales cálculos son posibles en las computadoras modernas, pero la gran magnitud de tales números hace que la velocidad de los cálculos disminuya considerablemente. A medida que $b$ y $e$ aumentan aún más para proporcionar una mejor seguridad, el valor $b e$ se vuelve difícil de manejar.

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

Método de uso eficiente de la 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, ahorrando tiempo (y también memoria) en general.

Este algoritmo hace uso de la identidad

(a \cdot b) módulo m = [(a módulo m) \cdot (b módulo m)] módulo m

El algoritmo modificado es:

Entradas Un entero $b$ (base), un entero $e$ (exponente) y un entero positivo $m$ (módulo)

Salidas El exponente modular $c$ donde

c = b e mod m

Inicializar $c = 1$ y buclear la variable $e' = 0$
Mientras que e′ < e do
1. Incrementar $e'$ en 1
2. Calcular $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)$ es verdadera. El algoritmo termina cuando el bucle se ha ejecutado $e$ veces. En ese punto, $c$ contiene el resultado de $b e mod m$ .

En resumen, este algoritmo incrementa $e'$ en uno hasta que es igual a $e$ . En cada paso, se multiplica el resultado de la iteración anterior, $c$ , por $b$ y se realiza una operación de módulo sobre el producto resultante, manteniendo así el resultado $c$ como un 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

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

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

Método binario de derecha a izquierda

Un tercer método reduce drásticamente el número de operaciones para realizar la exponenciación modular, manteniendo al mismo tiempo el mismo consumo 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 por cuadrado (también conocido como exponenciación binaria ).

En primer lugar, se requiere que el exponente $e$ se convierta 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 $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$ puede entonces escribirse 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}}

La solución $c$ es por tanto:

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 Criptografía Aplicada 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 Assert  :: (módulo - 1) * (módulo - 1) no desborda la base resultado := 1 base := base módulo módulo mientras exponente > 0 hacer  si (exponente módulo 2 == 1) entonces resultado := (resultado * base) módulo módulo exponente := exponente >> 1 base := (base * base) mod módulo devuelve resultado

Tenga en cuenta que al ingresar al 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 completarse cada bucle, la variable base sea equivalente a $b 2 i mod m$ , donde $i$ es la cantidad de veces que se ha iterado el bucle. (Esto hace que $i$ sea el siguiente bit de trabajo del exponente binario exponent , 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 por . $\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, inicialice el resultado a 1 y conserve el valor de $b$ en la variable $x$ : $R$

R\leftarrow 1\,(=b^{0}){\text{ and }}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 tanto no restablezca

R

;

colocar .

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

Paso 3) el bit 3 es 1, por lo tanto 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 tanto se establece ;

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

Este es el último paso, por lo que no necesitamos elevar

x

al cuadrado .

Hemos terminado: $R$ ahora es . $b^{13}$

Aquí está el cálculo anterior, donde calculamos $b = 4$ 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 tanto no restablezca

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 tanto 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 tanto 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(logaritmo del$ exponente $)$ . Al trabajar con valores grandes de exponente , esto ofrece una ventaja de velocidad sustancial sobre 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 pasos.

Implementación enLua

función modPow(b, e, m) si m == 1 entonces  devuelve 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 anterior fin  retorno r fin

Método binario de izquierda a derecha

También podemos utilizar los bits del exponente en orden de izquierda a derecha. En la práctica, normalmente querríamos que el resultado tuviera un módulo $m$ . En ese caso, reduciríamos cada resultado de multiplicación $(mód m)$ antes de continuar. Para simplificar, aquí se omite el cálculo del módulo. Este ejemplo muestra cómo realizar el cálculo utilizando la exponenciación binaria de izquierda a derecha. El exponente es 1101 en binario; hay 4 bits, por lo que hay 4 iteraciones. $b^{13}$

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

Paso 1) ; bit 1 = 1, por lo que se calcula ;

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

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

Paso 2) ; bit 2 = 1, por lo que se calcula ;

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, calcule .

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

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

Multiplicaciones mínimas

En The Art of Computer Programming , vol. 2, Seminumerical Algorithms , página 463, Donald Knuth señala que, contrariamente a algunas afirmaciones, este método no siempre da el mínimo número posible de multiplicaciones. El contraejemplo más pequeño es para una potencia de 15, cuando el método binario necesita seis multiplicaciones. En cambio, forme x ³ en dos multiplicaciones, luego x ⁶ elevando al cuadrado x ³ , luego x ¹² elevando al cuadrado x ⁶ , y finalmente x ¹⁵ multiplicando x ¹² y x ³ , logrando así el resultado deseado con solo cinco multiplicaciones. Sin embargo, siguen muchas páginas que describen cómo se pueden idear tales secuencias en general.

Generalizaciones

Matrices

El término $m$ -ésimo 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 de manera eficiente módulo $n$ calculando $A m mod n$ , donde $A es la$ matriz compañera $k \times k$ correspondiente . Los métodos anteriores se adaptan fácilmente a esta aplicación. Esto se puede utilizar para la prueba 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.

función Matrix_ModExp(Matriz 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 := Matriz_MódExp(A, b / 2, c) devuelve (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)$ simplemente se reemplaza en todas partes por la multiplicación de grupos $c = ab$ .

Exponenciación modular cuántica y reversible

En computación cuántica , la exponenciación modular aparece como el cuello de botella del algoritmo de Shor , donde debe ser calculada por un circuito que consta de puertas reversibles , que pueden descomponerse 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 ciencia 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 números enteros de precisión arbitraria tienen una función dedicada para realizar la exponenciación modular:

La función incorporada (exponenciación) de Pythonpow() [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 exponenciación modular
Función de MATLABpowermod de Symbolic Math Toolbox
Wolfram Language tiene la función PowerMod
El módulo de PerlMath::BigInt tiene un bmodpow()método [2] para realizar 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.
La calculadora HP Prime tiene la función CAS.powmod() [7] ^{[ vínculo inactivo permanente ]} 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.

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 y el ataque Logjam". weakdh.org . Consultado el 3 de mayo de 2019 .
^ Schneier 1996, pág. 244.
^ IL Markov, M. Saeedi (2012). "Circuitos cuánticos optimizados de manera constante para multiplicación y exponenciación modular". Información y computación cuántica . 12 (5–6): 0361–0394. arXiv : 1202.6614 . Código Bibliográfico :2012arXiv1202.6614M. doi :10.26421/QIC12.5-6-1. S2CID 16595181.

Enlaces externos

El Wikilibro Implementación de algoritmos tiene una página sobre el tema: Exponenciación modular

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). "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.