Test Foro de elhacker.net SMF 2.1

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

compartes el codigo fuente?

Claro

mira:



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:


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

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!

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