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