martes, 8 de mayo de 2012

Va a resultar que eres primo



Hoy vamos de pseudoprimos. Si recuerdas, el Pequeño teorema de Fermat afirma que si m es primo, se cumple que para todo a coprimo con m es verdadera esta congruencia:

am-1 º1 (mod m)

En cualquier manual puedes estudiarlo y seguir su demostración. Es recomendable igualmente visitar las páginas

http://mathworld.wolfram.com/FermatsLittleTheorem.html
http://hojamat.es/parra/modular.pdf
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf

El recíproco no es cierto. Si para un a primo con m se cumple am-1 º1 (mod m), entonces m no tiene que ser necesariamente primo. A estos números compuestos que cumplen el teorema les llamaremos pseudoprimos de Fermat para ese número a (hay otros, como los de Euler y los de Poulet, pero los dejamos para otra ocasión)

Hay algunos pseudoprimos que cumplen la condición am-1 º1 (mod m),  para todos los números primos con él. A estos números se les llama de números de Carmichael o pseudoprimos absolutos.

Vemos algún ejemplo de lo explicado:

91 pasa la prueba con 3 pero no es primo Es pseudoprimo para el 3. En efecto, lo vemos por duplicación de exponentes: 3º3 (mod 91), luego 32º9 (mod 91); 34º81 (mod 91); 38º9 (mod 91); 316º81 (mod 91); 332º9 (mod 91); 364º81 (mod 91) y queda
390=364+16+8+2º81*81*9*9º1 (mod 91);

Sin embargo, 91 no es primo, porque equivale a 7*13. Es pseudoprimo para el 3

Hemos presentado los números de Carmichael o primos absolutos. Son estos:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101,… (http://oeis.org/A002997)

En ellos la prueba de primalidad basada en el teorema de Fermat falla siempre. Por ejemplo, el 561 se daría como primo y resulta que es 561= 3* 11* 17. Volveremos sobre ellos más adelante.

Experimentación con hoja de cálculo

Los algoritmos aleatorios para intentar descubrir si N es primo, se basan en someterlo a la prueba del Pequeño Teorema con varios números aleatorios menores que N y primos con él. Si la prueba da positiva para todo ellos, le daremos a N el calificativo de “primo probable”, y si falla una vez, será con seguridad compuesto. Hemos construido un modelo con hoja de cálculo con objetivos puramente didácticos, sin ninguna otra pretensión. Confiamos que sirva de estímulo a quienes deseen profundizar más en el tema.



Como vemos en la imagen, se admite un número candidato a primo. Si resulta que es de Carmichael, se aconseja no seguir, aunque puedes hacerlo. Fijas el número de intentos aleatorios (en la imagen 17) y si en todos ellos se cumple am-1 º1 (mod m), se califica como primo posible. Si falla uno de ellos, con seguridad es compuesto.

El proceso es muy rápido porque hemos usado la exponenciación modular explicada en una entrada anterior.

Se ha añadido un botón para descomponer el número en factores primos y así tener la seguridad de que hemos acertado. Si el número es grande puede tardar mucho la comprobación, pero se puede abortar con la tecla ESC.

Puedes experimentar con él descargándolo desde la dirección

http://hojamat.es/blog/pseudoprimos.xslm

Nuestro deseo es que te aficiones a estos temas de los criterios de primalidad. Hay mucho escrito sobre eso y puede hasta ser divertido.




No hay comentarios: