Título: Multiple Exponeciacion y Modulacion Publicado por: AlbertoBSD en 3 Octubre 2009, 17:27 pm Suponemos que existe un algoritmo que puede calcular el modulo n de Xp donde p es potenciado ala ( pp) 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 X2 Sin embargo yo tengo Xp 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 Título: Re: Multiple Exponeciacion y Modulacion Publicado por: isseu en 3 Octubre 2009, 17:31 pm compartes el codigo fuente?
Título: Re: Multiple Exponeciacion y Modulacion Publicado por: AlbertoBSD en 3 Octubre 2009, 18:02 pm Claro
mira: Código El archivo de entrada tiene lo siguiente: Código: 3 3 1 5 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 Título: Re: Multiple Exponeciacion y Modulacion Publicado por: do-while en 4 Octubre 2009, 15:33 pm 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! Título: Re: Multiple Exponeciacion y Modulacion Publicado por: AlbertoBSD en 11 Octubre 2009, 04:19 am 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 |