Diferencia entre revisiones de «Implementación de algoritmos de teoría de números/Exponenciación modular»
Contenido eliminado Contenido añadido
+sección |
+implementaciones |
||
Línea 55:
base := (base * base) '''mod''' modulus
'''return''' result
== Implementaciones ==
=== C ===
==== Algoritmo de derecha a izquierda ====
<source lang="c">
long powmod(long a, long e, long n){
long accum = 1, apow, x;
apow = a; x = e;
while(x != 0){
if (x & 0x01){ accum = (accum*apow) % n;};
x >>= 1;
apow = (apow * apow) % n;
};
return accum;
}
</source>
==== Algoritmo de derecha a izquierda con GMP ====
La biblioteca GMP tiene una función <code>mpz_powm(result,a,e,n)</code>, así que no es necesaria esta implementación, pero se muestra aquí como método explicativo.
<source lang="c">
// High to Low powmod algorithm
int powmod(mpz_t result, mpz_t a, mpz_t e, mpz_t n) {
// Use result as accum (temp variable)
if (mpz_cmp_si(e,0) == 0) { // If exponent is zero
mpz_set_ui(result, 1); // Set result to 1
return 1;
};
mpz_set(result, a); // Set value of accum to a
int bitptr = mpz_sizeinbase(e,2) - 1; // Find top bit in exponent
for(bitptr--; bitptr >= 0; bitptr--) {
mpz_mul(result,result,result); // result <-- result^2
mpz_fdiv_r(result,result,n); // result <-- result (mod n)
if(mpz_tstbit(e,bitptr)) { // Is bit e[bitptr] == 1?
mpz_mul(result,result,a); // result <-- result*a
mpz_fdiv_r(result,result,n); // result <-- result (mod n)
};
};
return 1;
}
</source>
=== Java ===
==== Algoritmo de derecha a izquierda ====
<source lang="java">
public static long powmod(long a, long e, long n){
long accum = 1;
long x = e;
long apow = a;
while (x != 0){
if ((x & 0x01) == 0x01){
accum = (accum * apow) % n;
};
x >>= 1;
apow = (apow * apow) % n;
};
return accum;
}
</source>
==== Algoritmo de derecha a izquierda con BigInteger ====
La clase BigInteger de Java tiene un método <code>modPow(e, n)</code>, así que no es necesaria esta implementación, pero se muestra aquí como método explicativo.
<source lang="java">
// High to low powmod algorithm
public static BigInteger POWMOD(BigInteger a, BigInteger e, BigInteger n) {
BigInteger accum = a;
if (e.equals(BigInteger.ZERO)) {return BigInteger.ONE;};
int bitptr = e.bitLength()-1;
for(bitptr--; bitptr >= 0; bitptr--){
accum = accum.multiply(accum).mod(n);
if(e.testBit(bitptr)){
accum = accum.multiply(a).mod(n);
};
};
return accum;
}
</source>
=== Python ===
==== Algoritmo de derecha a izquierda ====
Python tiene una función <code>pow(a, e, n)</code>, así que no es necesaria esta implementación, pero se muestra aquí como método explicativo.
<source lang="python">
def powmod(a,e,n):
accum = 1; i = 0; apow2 = a
while ((e>>i)>0):
if ((e>>i) & 1):
accum = (accum*apow2) % n
apow2 = (apow2*apow2) % n
i += 1
return accum
</source>
== Referencias ==
| |||