Multiple Exponeciacion y Modulacion

[AlbertoBSD]

Suponemos que existe un algoritmo que puede calcular el modulo n de X^p donde p es potenciado ala ( p^p) esto m veces.

Alguna solucion he visto un articulo similar en wikipedia http://en.wikipedia.org/wiki/Quadratic_residue

Donde ahi sacan el modulo de X² Sin embargo yo tengo X^p donde p es elevado a la p m veces.

Cabe mencionar que X y P siempre son numero primos he hecho el programa usando java y el BigInteger, sin embargo al trabajar con numeros grandes no pasa del segundo ciclo de exponenciacion de los m - 2 restantes.

Saludos

[isseu]

compartes el codigo fuente?

[AlbertoBSD]

Claro

mira:

Código (java) [Seleccionar] Expandir



import java.io.FileReader;
import java.io.BufferedReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Problem1 {

public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("q1.txt"));
StringTokenizer st;
BigInteger a, p, m, n,pm;
int i;
while(in.ready()) {
st = new StringTokenizer(in.readLine());
a = new BigInteger(st.nextToken());
p = new BigInteger(st.nextToken());
m = new BigInteger(st.nextToken());
n = new BigInteger(st.nextToken());
System.out.println("a = "+ a);
System.out.println("p = "+ p);
System.out.println("m = "+ m);
System.out.println("n = "+ n);
i = 1;
pm = new BigInteger(p.toString());

while(i < m.intValue()) {
System.out.println("pass: " + i);
pm = pm.pow(p.intValue());
i++;
}
System.out.println("p^p m veces = "+ pm);
System.out.println("Resultado: "+a.modPow(pm,n));
}
}
}
El archivo de entrada tiene lo siguiente:

Código [Seleccionar] Expandir


3 3 1 5
3 3 2 5
3 3 3 5
47 47 1 67
47 47 2 67
47 47 3 67
32719 54323 99 65399

Los primeros 6 lineas las procesa rapido pero la ultima, no pasa del sugundo ciclo como mencione.

El problema original esta descrito aqui:


:http://acmicpc-live-archive.uva.es/nuevoportal/data/p2046.pdf

:http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2046


Saludos

[do-while]

Hola.

Si tienes que a = x mod(n) tendras que a^k = x^k mod(n), ya que el conjunto de valores mod(n) de los enteros forma un anillo.

Ahora si tienes a^k donde k=p^m, tendras que:

si x^k = y mod(n) -> a^k = x^k mod(n) = x^(p^m) mod(n) = (x^p)^m mod(n)

Ahora obtendras que x^p = y mod(n), por lo tanto: x^k = y^m mod(n), y solo tendras que calcular y^m mod(n) = z

resumiendo:

a^(p^m) -> los datos son a,p y m.

calculas x = a mod(n) (Asi reduces la base)
calculas x^p (como la base esta reducida, tardara menos (supongo))
calculas y = x^p mod(n) (Vuelves a reducir la base)
calculas z = y^m mod(n)

y z es el resultado que buscabas.

Espero que esto te simplifique las cosas.

Hasta luego!

[AlbertoBSD]

Muchas Gracias la verdad no tencia todo bien claro sobre la modulacion, pero ya con tu explicacion esta mejor, tambien he seguido leyendo en wikipedia y libros de matematicas donde manejan el tema.

Sin embargo checa bien el pdf que puse en uno de los links anteriores, el problema aqui es la exponeciacion P a la P a la P a la P .... M veces lo anterior.

Seguire haciendo ejemplo con lo que mencioanastes para ver hasta donde llego.

Saludos y gracias