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

Por exemplo, dados Modelo:Math, Modelo:Math e Modelo:Math, dividindo Modelo:Math por Modelo:Math deixa un resto de Modelo:Math. Escrito modularmente$5^3\equiv 8(\mathrm{mod}13)$.

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

$b^{-e}\equiv c(\mathrm{mod}m)$ sería $d^e\equiv c(\mathrm{mod}m)$ con $b\cdot d\equiv 1(\mathrm{mod}m)$.

Por exemplo $3^{-4}\equiv 2(\mathrm{mod}7)$ pois $5^4\equiv 2(\mathrm{mod}7)$ sendo $3\cdot 5\equiv 1(\mathrm{mod}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 Modelo:Math cando se dan Modelo:Math, Modelo:Math e Modelo:Math. 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

Modelo:Math.

Consiste en procurar a potencia $e_1$ de Modelo:Mvar máis próxima ao módulo Modelo:Mvar, calcular o módulo de $b^{e_1}\equiv c_1(\mathrm{mod}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(\mathrm{mod}497)$

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

$30^2\cdot 4^3=57600\equiv 445(\mathrm{mod}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(\mathrm{mod}497)\text{ implica }{4}^{13}\equiv c(\mathrm{mod}497)$.

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

$2^3\equiv -1(\mathrm{mod}7)$ e $13=4\cdot 3+1$,

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

Método directo

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

$4^{13}\equiv c(\mathrm{mod}497)$

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

Teña en conta que Modelo:Math ten só un díxito de lonxitude e que Modelo:Math só ten dous díxitos de lonxitude, mais o valor Modelo:Math é de 8 díxitos. E no caso de $501^{13}\equiv c(\mathrm{mod}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

Modelo:Math

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

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

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

Modelo:Math

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

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

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

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

$c\equiv \prod _{i=0}^{n-1}{b}^{a_i{2}^i}(\mathrm{mod}m)$

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

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

$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(\mathrm{mod}497)$ ;

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

Paso 2) o bit 2 é 0, polo que non recalculamos Modelo:Math;

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

Paso 3) o bit 3 é 1, así que recalculamos Modelo:Math

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

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

Paso 4) o bit 4 é 1, así que recalculamos Modelo:Math

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

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

Xeneralizacións

Matrices

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

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita publicación periódica

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