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 cuando un número entero $b$ (la base) se eleva a la potencia $e$ (el exponente) y se divide por un número entero positivo $m$ (el módulo); es decir, $c = b mi 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$ , dividir $53 = 125$ por $13$ deja un resto de $c = 8$ .

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 . Eso es:

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

, donde

e < 0

b \cdot d \equiv 1 (mod m)

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

c \equiv 4 13 (mod 497)

Se podría usar una calculadora para calcular 4 ¹³ ; esto equivale 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 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 sólida, $b$ suele tener al menos 1024 bits . ^[1] Considere $b = 5 \times 10 76$ y $e = 17$ , los cuales son valores perfectamente razonables. En este ejemplo, $b$ tiene una longitud de 77 dígitos y $e$ tiene una longitud de 2 dígitos, pero el valor $b e$ tiene una longitud de 1304 dígitos decimales. Estos cálculos son posibles en las computadoras modernas, pero la magnitud de tales números hace que la velocidad de los cálculos se reduzca considerablemente. A medida que $b$ y $e$ aumentan aún más para proporcionar una mayor 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 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, lo que ahorra tiempo (y memoria) en general.

Este algoritmo hace uso de la identidad.

(a \cdot b) mod m = [(a mod m) \cdot (b mod m)] mod 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

Inicialice $c = 1$ y repita la variable $e' = 0$
Mientras e ′ < e hacer
1. Incrementar $e'$ en 1
2. Calcular $c = (b \cdot c) mod m$
Salida $c$

Tenga en cuenta que al final de cada iteración a través del bucle, la ecuación $c \equiv b e' (mod m)$ es válida. El algoritmo finaliza cuando el bucle se ha ejecutado $e$ veces. En ese punto $c$ contiene el resultado de $b e mod m$ .

En resumen, este algoritmo aumenta $e'$ en uno hasta que sea igual a $e$ . En cada paso, multiplicar el resultado de la iteración anterior, $c$ , por $b$ y realizar una operación de módulo en el producto resultante, manteniendo así el $c$ resultante 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 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 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 módulo = 1 entonces  devuelve 0 c := 1 para e_prime = 0 al exponente-1 do c := (c * base) módulo mod return 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 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 conocida como exponenciación binaria ).

Primero, se requiere convertir el exponente e $a$ notación binaria . Es decir, $e$ puede escribirse como:

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

En tal notación, la longitud de $e$ es $n$ bits. $a i$ puedo tomar el valor 0 o 1 para cualquier $i$ tal que $0 \leq i < n$ . Por definición, $una norte - 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 Afirmar  :: (módulo - 1) * (módulo - 1) no desborda la base resultado := 1 base: = módulo mod base mientras que exponente> 0 hazlo  si ( mod exponente 2 == 1) entonces resultado: = (resultado * base) módulo mod exponente := exponente >> 1 base := (base * base) resultado de retorno del módulo mod

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 finalizar cada bucle, la base variable sea equivalente a $b 2 i mod m$ , donde $i$ es el número de veces que se ha iterado el bucle. (Esto convierte $a i$ en el siguiente bit de trabajo 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 $un$ $\prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}$ es cero, no se ejecuta ningún código ya que esto efectivamente multiplica el total acumulado por uno. si $un$ en lugar de uno, la base 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 en 1 y conserva 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, así que configúrelo ;

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

colocar .

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

Paso 2) el bit 2 es 0, así que no reinicie

R

;

colocar .

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

Paso 3) el bit 3 es 1, así que configúrelo ;

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

colocar .

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

Paso 4) el bit 4 es 1, así que configúrelo ;

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

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

x

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

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

Inicializar:

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

y .

x\leftarrow b=4

Paso 1) el bit 1 es 1, así que configúrelo ;

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, así que no reinicie

R

;

colocar .

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

Paso 3) el bit 3 es 1, así que configúrelo ;

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, así que configúrelo ;

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 ($ 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 ²⁰ = 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 final  local r = 1 segundo = segundo % metro mientras e > 0 hazlo  si e % 2 == 1 entonces r = (r*b)% metro fin segundo = (b*b) % metro e = e >> 1 --use 'e = math.floor(e / 2)' en Lua 5.2 o anterior fin  regresar 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 que el resultado fuera un 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 calcular usando exponenciación binaria de izquierda a derecha. El exponente es 1101 en binario; hay 4 bits, por lo que hay 4 iteraciones. $b^{13}$

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

Paso 1) ; bit 1 = 1, entonces calcule ;

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

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

Paso 2) ; bit 2 = 1, entonces calcule ;

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

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

Paso 3) ; bit 3 = 0, entonces hemos terminado con este paso;

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

Etapa 4) ; bit 4 = 1, entonces calcule .

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 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 su lugar, 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, a continuación aparecen muchas páginas que describen 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 $k$ términos anteriores se puede calcular eficientemente módulo $n calculando Am$ $mod$ n $, donde A$ es $el$ $k$ correspondiente $\times$ $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)= $Ab 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 de identidad si (b mod 2 == 1) luego  devuelve (A * Matrix_ModExp(A, b - 1, c) ) mod c Matriz D := Matrix_ModExp(A, b / 2, c) retorno (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 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 la computación cuántica , la exponenciación modular aparece como el cuello de botella del algoritmo de Shor , donde debe calcularse mediante 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 diversas optimizaciones del circuito. ^[3]

Implementaciones de software

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Exponenciación modular

Debido a que la exponenciación modular es una operación importante en 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 pow()(exponenciación) de Python [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 la exponenciación modular
Raku tiene una rutina incorporada expmod.
El tipo de Gobig.Int contiene un Exp()método (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 Rubyopenssl tiene el OpenSSL::BN#mod_expmétodo [6] para realizar una exponenciación modular.
La calculadora HP Prime tiene la función CAS.powmod() [7] ^{[ enlace muerto permanente ]} para realizar la 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

^ "El débil Diffie-Hellman y el ataque Logjam". débildh.org . Consultado el 3 de mayo de 2019 .
^ Schneier 1996, pág. 244.
^ IL Markov, M. Saeedi (2012). "Circuitos cuánticos optimizados constantemente para multiplicación y exponenciación modulares". Información y Computación Cuántica . 12 (5–6): 0361–0394. arXiv : 1202.6614 . Código Bib : 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, subprograma Java de exponenciación modular rápida
Gordon, Daniel M. (1998). "Un estudio sobre 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.