Autor Tema: Números de Carmichael y ptf

0 Usuarios y 1 Visitante están viendo este tema.

18 Julio, 2010, 10:24 pm
Leído 1926 veces

josepil

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 38
  • Karma: +0/-1
  • Sexo: Masculino
Buenas, estaba haciendo un problema de programación  que dice, los números de Carmichael son aquellos que son números compuestos y pasan el test de primalidad de Fermat el cual dice \( a^n mod n = a  \)para todo \( a<n \) donde n es el primo probable, dado un n decir si es un numero de Carmichael, el problema es que el n puede ser menor igual que 65000 y este número es muy grande para que lo soporte la memoria, mi pregunta es existe alguna forma de evitar calcular la potencia y saber si ese número es un número de Carmichael, gracias

19 Julio, 2010, 11:15 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Hay algoritmos para calcular potencias en arimética modular más eficientes que hacer la potencia y luego reducir en módulo.

 Mira por aquí:

http://en.wikipedia.org/wiki/Modular_exponentiation

Saludos.

19 Julio, 2010, 11:26 am
Respuesta #2

bepro

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 331
  • Karma: +0/-0
  • Sexo: Masculino
    • GENERALIZACION DE LA REGLA DE RUFFINI
Yo creo que la definición de número de Carmichael está equivocada, voy a dar la definición corrects. Sea \( n\geq{3} \) un número compuesto, impar y no cuadrado, entonces para cada divisor primo p de n, tenemos que (p-1)|(n-1), entonces n es un número de Carmichael.

19 Julio, 2010, 11:37 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Ambas definiciones son equivalentes.

 La segunda, la de bepro, se llama el Teorema o critero de Korselt.

Saludos.

P.D. Puede leerse algo sobre el tema aquí:

http://en.wikipedia.org/wiki/Carmichael_number

20 Julio, 2010, 09:57 pm
Respuesta #4

josepil

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 38
  • Karma: +0/-1
  • Sexo: Masculino
Gracias por el enlace me ha servido de mucho, tengo otra preguntica, es posible afirmar que un numero par no puede ser un numero de carmichael?