Exponenciación modular

A exponenciación modular é a exponenciación realizada sobre un módulo. É útil en informática, especialmente no campo da criptografía de clave pública, onde se usa tanto no intercambio de claves Diffie-Hellman como nas claves públicas/privadas RSA.

A exponenciación modular é o resto cando un enteiro b (a base) elévase á potencia e (o expoñente) e se divide por un enteiro positivo m (o módulo); é dicir, $b^{e}\equiv c{\pmod {m}}$, onde 0 ≤ c < m .

Por exemplo, dados b = 5, e = 3 e m = 13, dividindo 5³ = 125 por 13 deixa un resto de c = 8. Escrito modularmente$5^{3}\equiv 8{\pmod {13}}$.

A exponenciación modular pódese realizar cun expoñente negativo atopando a inversa multiplicativa modular d de b módulo m usando o algoritmo de Euclides estendido. É dicir:

$b^{-e}\equiv c{\pmod {m}}$ sería $d^{e}\equiv c{\pmod {m}}$ con $b\cdot d\equiv 1{\pmod {m}}$.

Por exemplo $3^{-4}\equiv 2{\pmod {7}}$ pois $5^{4}\equiv 2{\pmod {7}}$ sendo $3\cdot 5\equiv 1{\pmod {7}}$.

O cálculo da exponenciación modular é eficiente, mesmo para enteiros moi grandes. Por outra banda, é difícil calcular o logaritmo discreto modular, é dicir, atopar o expoñente e cando se dan b, c e m. Este comportamento de función unidireccional fai que a exponenciación modular sexa candidata para o seu uso en algoritmos criptográficos.

Método de módulo próximo

Este método usa a propiedade modular seguinte

(a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m.

Consiste en procurar a potencia $e_{1}$ de b máis próxima ao módulo m, calcular o módulo de $b^{e_{1}}\equiv c_{1}{\pmod {m}}$ e calculando a división enteira dos expoñentes ${\frac {e}{e_{1}}}{\text{ con }}e=e_{1}\cdot d+r$ transformamos a expresión orixinal con cifras moito menores.

Exemplo: $4^{13}\equiv c{\pmod {497}}$

$4^{5}=1024$ e $13=2\cdot 5+3$ e tamén $1024\equiv 30{\pmod {497}}$

$30^{2}\cdot 4^{3}=57600\equiv 445{\pmod {497}}$.

Por tanto $c=445$.

Se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: $501^{13}\equiv c{\pmod {497}}{\text{ implica }}4^{13}\equiv c{\pmod {497}}$.

Este método tamén podería aproximar a equivalencias negativas, por exemplo para $2^{13}\equiv c{\pmod {7}}$, temos:

$2^{3}\equiv -1{\pmod {7}}$ e $13=4\cdot 3+1$,

$(-1)^{4}\cdot 2\equiv 2{\pmod {7}}$ e por tanto $c=2$

Método directo

O método máis directo de calcular un expoñente modular é calcular b^e e despois tomar este número módulo m. Co exemplo anterior temos:

$4^{13}\equiv c{\pmod {497}}$

Calculando 4¹³ = 67 108 864. Tomando este valor módulo 497, a resposta c determínase que é 445.

Teña en conta que b ten só un díxito de lonxitude e que e só ten dous díxitos de lonxitude, mais o valor b^e é de 8 díxitos. E no caso de $501^{13}\equiv c{\pmod {497}}$ se non reducimos a base previamente temos $501^{13}$ unha cifra de 35 díxitos.

Método de memoria eficiente

Manter os números máis pequenos require operacións de redución modulares adicionais, mais o tamaño reducido fai que cada operación sexa máis rápida, aforrando tempo (así como memoria) en xeral.

Este algoritmo tamén fai uso da identidade

(a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

En resumo, este algoritmo aumenta e′ nunha unidade ata que sexa igual a e. En cada paso multiplicando o resultado da iteración anterior, c, por b e realizando unha operación de módulo sobre o produto resultante, mantendo así o c resultante nun número enteiro pequeno.

Preséntase de novo o exemplo b = 4, e = 13 e m = 497. O algoritmo realiza a iteración trece veces:

(e′ =  1)   c = (4 ⋅ 1) mod 497 = 4 mod 497 = 4

(e′ =  2)   c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16

(e′ =  3)   c = (4 ⋅ 16) mod 497 = 64 mod 497 = 64

(e′ =  4)   c = (4 ⋅ 64) mod 497 = 256 mod 497 = 256

(e′ =  5)   c = (4 ⋅ 256) mod 497 = 1024 mod 497 = 30

(e′ =  6)   c = (4 ⋅ 30) mod 497 = 120 mod 497 = 120

(e′ =  7)   c = (4 ⋅ 120) mod 497 = 480 mod 497 = 480

(e′ =  8)   c = (4 ⋅ 480) mod 497 = 1920 mod 497 = 429

(e′ =  9)   c = (4 ⋅ 429) mod 497 = 1716 mod 497 = 225

(e′ = 10)   c = (4 ⋅ 225) mod 497 = 900 mod 497 = 403

(e′ = 11)   c = (4 ⋅ 403) mod 497 = 1612 mod 497 = 121

(e′ = 12)   c = (4 ⋅ 121) mod 497 = 484 mod 497 = 484

(e′ = 13)   c = (4 ⋅ 484) mod 497 = 1936 mod 497 = 445

A resposta final para c é polo tanto 445, como no método directo e o método de módulo próximo.

Método binario de dereita a esquerda

Un cuarto método reduce drasticamente o número de operacións para realizar a exponenciación modular, mantendo o mesmo uso de memoria que no método anterior. É unha combinación do método anterior e un principio máis xeral chamado exponenciación binaria.

En primeiro lugar, é necesario que o expoñente e se converta en notación binaria. É dicir, e pódese escribir como:

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

En tal notación, a lonxitude de e é n bits. a_i pode tomar o valor 0 ou 1 para calquera i tal que 0 ≤ i < n . Por definición, a_{n − 1} = 1 .

O valor b^e 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}}$

A solución c é polo tanto:

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

Neste exemplo, a base b elévase ata o expoñente e = 13 . O expoñente é 1101 en binario. Hai catro díxitos binarios, polo que o bucle execútase catro veces, cos valores a₀ = 1, a₁ = 0, a₂ = 1 e a₃ = 1 .

Primeiro, inicializa o resultado $R$ a 1 e garda o valor de b na variable x:

$R\leftarrow 1\,(=b^{0})$ e $x\leftarrow b=4$ .

Paso 1) o bit 1 é 1, así que se estabelece

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

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

Paso 2) o bit 2 é 0, polo que non recalculamos R;

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

Paso 3) o bit 3 é 1, así que recalculamos R

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

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

Paso 4) o bit 4 é 1, así que recalculamos R

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

Resultado $c=497$ igual que nos métodos anteriores.

Xeneralizacións

Matrices

O m-ésimo termo de calquera secuencia recursiva constante (como os números de Fibonacci ou os números de Perrin) onde cada termo é unha función linear de k termos anteriores pódese calcular eficientemente módulo n calculando A^m mod n, onde A é matriz compañeira k×k correspondente . Os métodos anteriores adáptanse facilmente a esta aplicación. Isto pódese usar para os test de primalidade de grandes números n, por exemplo.

Véxase tamén

Bibliografía

• Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4. 
• Gordon, Daniel M. (1998). "A Survey of Fast Exponentiation Methods" (PDF). Journal of Algorithms (Elsevier BV) 27 (1): 129–146. ISSN 0196-6774. doi:10.1006/jagm.1997.0913. 

Outros artigos

• Redución de Montgomery, para calcular o resto cando o módulo é moi grande.
• Multiplicación de Kochanski, método serializábel para calcular o resto cando o módulo é moi grande
• Redución de Barrett, algoritmo para calcular o resto cando o módulo é moi grande.

Ligazóns externas

• Paul Garrett, Fast Modular Exponentiation Java Applet