elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Multiple Exponeciacion y Modulacion
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Multiple Exponeciacion y Modulacion  (Leído 4,687 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Multiple Exponeciacion y Modulacion
« 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


En línea

isseu


Desconectado Desconectado

Mensajes: 325


°º¤ø,¸¸,El conocimiento es poder°º¤ø,¸¸,ø¤º°`°º¤ø,


Ver Perfil WWW
Re: Multiple Exponeciacion y Modulacion
« Respuesta #1 en: 3 Octubre 2009, 17:31 pm »

compartes el codigo fuente?


En línea

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Multiple Exponeciacion y Modulacion
« Respuesta #2 en: 3 Octubre 2009, 18:02 pm »

Claro

mira:

Código
  1.  
  2. import java.io.FileReader;
  3. import java.io.BufferedReader;
  4. import java.math.BigInteger;
  5. import java.util.StringTokenizer;
  6.  
  7. public class Problem1 {
  8.  
  9. public static void main(String args[]) throws Exception {
  10. BufferedReader in = new BufferedReader(new FileReader("q1.txt"));
  11. BigInteger a, p, m, n,pm;
  12. int i;
  13. while(in.ready()) {
  14. st = new StringTokenizer(in.readLine());
  15. a = new BigInteger(st.nextToken());
  16. p = new BigInteger(st.nextToken());
  17. m = new BigInteger(st.nextToken());
  18. n = new BigInteger(st.nextToken());
  19. System.out.println("a = "+ a);
  20. System.out.println("p = "+ p);
  21. System.out.println("m = "+ m);
  22. System.out.println("n = "+ n);
  23. i = 1;
  24. pm = new BigInteger(p.toString());
  25.  
  26. while(i < m.intValue()) {
  27. System.out.println("pass: " + i);
  28. pm = pm.pow(p.intValue());
  29. i++;
  30. }
  31. System.out.println("p^p m veces = "+ pm);
  32. System.out.println("Resultado: "+a.modPow(pm,n));
  33. }
  34. }
  35. }
El archivo de entrada tiene lo siguiente:

Código:
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



En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Multiple Exponeciacion y Modulacion
« Respuesta #3 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!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Multiple Exponeciacion y Modulacion
« Respuesta #4 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
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines