Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Exponenciación modular»

Contenido eliminado Contenido añadido
Raulshc (discusión | contribs.)
+sección
Raulshc (discusión | contribs.)
+sección
Línea 23:
c := (c * base) '''mod''' modulus
'''return''' c
 
== Método binario derecha a izquierda ==
 
Este método reduce drásticamente el número de operaciones para realizar la exponenciación modular, mientras se mantiene la misma cantidad de memoria que en el método anterior. Es una combinación del método anterior y un principio más general llamado exponenciación por cuadrados (más conocido como ''exponenciación binaria'').
 
Primero, se requiere que el exponente ''e'' sea convertido a notación binaria. Esto es, ''e'' puede ser escrito como:
: <math>e = \sum_{i=0}^{n-1} a_i 2^i</math>
 
En tal notación, la ''longitud'' de ''e'' is ''n'' bits. ''a''<sub>''i''</sub> puede tomar el valor de 0 o 1 para cualquier ''i'' tal que 0 ≤ ''i'' < ''n''. Por definición, ''a''<sub>''n'' − 1</sub> {{=}} 1.
 
El valor ''b''<sup>''e''</sup> puede ser escrito entonces como:
: <math>b^e = b^{\left( \sum_{i=0}^{n-1} a_i 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}</math>
 
La solución ''c'' es por lo tanto:
: <math>c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)</math>
 
=== Pseudocódigo ===
 
Un ejemplo en pseudocódigo basado de Applied Cryptography por Bruce Schneier.<ref name="schneier96p244">[[#Schneier96|Schneier 1996]], p. 244.</ref> Las entradas <var>base</var>, <var>exponent</var>, y <var>modulus</var> corresponden a ''b'', ''e'', y ''m'' en las ecuaciones dadas anteriormente.
 
'''function''' modular_pow(base, exponent, modulus) '''is'''
'''if''' modulus = 1 '''then'''
'''return''' 0
[[Assertion (computing)|Assert]] :: (modulus - 1) * (modulus - 1) does not overflow base
result := 1
base := base '''mod''' modulus
'''while''' exponent > 0 '''do'''
'''if''' (exponent '''mod''' 2 == 1) '''then'''
result := (result * base) '''mod''' modulus
exponent := exponent >> 1
base := (base * base) '''mod''' modulus
'''return''' result
 
== Referencias ==
<references/>
 
[[Categoría:Libro:Implementación de algoritmos de teoría de números]]