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

Por exemplo, dados ,  e , dividindo  por  deixa un resto de . Escrito modularmente, .

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:

  sería  con . 

Por exemplo  pois  sendo .

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  de  máis próxima ao módulo , calcular o módulo de  e calculando a división enteira dos expoñentes    transformamos a expresión orixinal con cifras moito menores.

Exemplo: 

  e     e tamén  
. 

Por tanto .

Se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: .

Este método tamén podería aproximar a equivalencias negativas, por exemplo para , temos:
  e ,

  e por tanto 

 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:

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  se non reducimos a base previamente temos  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:



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:



A solución  é polo tanto:



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  a 1 e garda o valor de  na variable :

  e  .
 Paso 1) o bit 1 é 1, así que se estabelece 
 ;
 agora  .
 Paso 2) o bit 2 é 0, polo que non recalculamos ;
 así  .
 Paso 3) o bit 3 é 1, así que recalculamos  
;
 agora .
 Paso 4) o bit 4 é 1, así que recalculamos   
 ;

Resultado  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

Categoría:Teoría de números