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  (a base) elévase á potencia  (o expoñente) e se divide por un enteiro positivo  (o módulo); é dicir, b^e \equiv c \pmod{m}, onde  .

Por exemplo, dados ,  e , dividindo  por  deixa un resto de . Escrito modularmente, 5^3 \equiv 8 \pmod{13}.

A exponenciación modular pódese realizar cun expoñente *negativo* atopando a inversa multiplicativa modular  de  módulo  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  cando se dan ,  e . 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

.

Consiste en procurar a potencia e_1 de  máis próxima ao módulo , 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  e despois tomar este número módulo . Co exemplo anterior temos:

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

:

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

Teña en conta que  ten só un díxito de lonxitude e que  só ten dous díxitos de lonxitude, mais o valor  é 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

: 

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

Preséntase de novo o exemplo ,  e . O algoritmo realiza a iteración trece veces:

: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 

A resposta final para  é 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  se converta en notación binaria. É dicir,  pódese escribir como:

: e = \sum_{i=0}^{n-1} a_i 2^i

En tal notación, a *lonxitude* de  é  bits.  pode tomar o valor 0 ou 1 para calquera  tal que  . Por definición,  .

O valor  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  é polo tanto:

: c \equiv \prod_{i=0}^{n-1} b^{a_i 2^i} \pmod m

Neste exemplo, a base  elévase ata o expoñente  . O expoñente é 1101 en binario. Hai catro díxitos binarios, polo que o bucle execútase catro veces, cos valores  e  .

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

:  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 ;
:: 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 \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 \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 -é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  termos anteriores pódese calcular eficientemente módulo  calculando , onde  é  matriz compañeira  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 , por exemplo.

## Notas 
## Véxase tamén 
### Bibliografía 
*
* 
### 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