Definición de pseudoprimo
La idea de número pseudoprimo surge de los grandes teoremas de la Aritmética Modular
(Ver mi publicación http://www.hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf):
Podemos comenzar por el de Euler: Si llamamos j(m) a la indicatriz de Euler de m, se cumplirá
que
aj(m) =1 (mod m)
para todo a
primo con m. (Teorema de Euler)
Si m es primo,
la igualdad anterior se puede expresar como
am-1 =1 (mod
m)
(Pequeño Teorema de Fermat)
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 (hay otras clases de pseudoprimos). Este carácter dependerá del
valor de la base a.
Identificación
de pseudoprimos
No es nada complicado identificar un pseudoprimo respecto
a una base dada. Las operaciones son sencillas, pero pueden alcanzar números
muy grandes, por lo que tendremos que usar técnicas de Aritmética Modular en
algunos casos, para abreviar cálculos y datos.
La primera operación es la de obtener el resto de una
potencia respecto a un módulo, lo que llamamos resto potencial. En
nuestra web figura una hoja de cálculo de hace años, muy simple, que los
calcula para datos no muy grandes
http://www.hojamat.es/sindecimales/congruencias/herramientas/hoja/potenciales.xls
La teoría sobre restos potenciales también la puedes
consultar en nuestro documento
http://www.hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf
Aquí partiremos de una función que actuará sobre tres
datos:
- · Base
de la potencia b
- · Exponente
p
- · Módulo
m
Sobre ellos actuará la función RESTOPOT para Excel y LibreOffice Calc, que irá construyendo la potencia mediante multiplicaciones, pero convirtiendo cada resultado en resto módulo m, con lo que no se disparará la magnitud de los datos. Este es su listado:
Función RESTOPOT
Public Function restopot(b, p, n)
Dim r, m, i
r = b Mod n ‘Resto
de la base respecto a m
m = 1
For i = 1 To p ‘Se
construye la potencia con restos
m = m * r Mod n ‘m irá recorriendo los restos
potenciales
Next i
restopot = m
End Function
Con esta función podemos averiguar si am-1 =1 (mod m)
y si m es compuesto, con lo
que tendría el carácter de pseudoprimo.
Contando con la función RESTOPOT es fácil exigir que se
cumplan las condiciones para ser pseudoprimo en una base dada.
Public
Function espseudo(m, b) As Boolean
If
Not esprimo(m) And mcd(m, b) = 1 And restopot(b, m - 1, m) = 1 Then espseudo =
True Else espseudo = False
End
Function
Nos limitamos a exigir que
- · Sea
compuesto
- · Primo
con la base
- · El
resto potencial bm-1
respecto a m sea 1
Con esta función y un bucle de búsqueda podemos
reproducir muchas sucesiones de pseudoprimos ya publicadas en OEIS. Por
ejemplo, para b=23 obtenemos esta lista:
Pseudoprimos
en base 23
22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481,…
La puedes comprobar en http://oeis.org/A020151
En
base 11
Obtenemos: 10, 15, 70, 133, 190, 259, 305, 481, 645, 703,
793, 1105, 1330, 1729, 2047, 2257
(Ver http://oeis.org/A020139)
Versión
en PARI
Si deseas estudiar números mayores contando con la mayor
velocidad de proceso de PARI, puedes usar este código debidamente adaptado a
tus datos (está construido para base 23 y búsqueda hasta el 4000):
rpm(b,p,n)={my(r,m,i);r=b%n;m=1;for(i=1,p,m=(m*r)%n);m}
espseudo(m,b)=!isprime(m)&&gcd(m,b)==1&&rpm(b,m-1,m)==1
for(k=2,4000,if(espseudo(k,23),print1(k,",
")))
Lo hemos adaptado a base 17 y cota 20000, obteniendo:
4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305,
1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601,
6697, 7171, 8481, 8911, 10585, 11476, 12403, 12673, 13333, 13833, 15805, 15841,
16705, 19345, 19729,…
Coinciden con los pseudoprimos publicados en http://oeis.org/A020145
Números
de Carmichael
Si un número es pseudoprimo con base todos los números
coprimos con él, se llama “de Carmichel”.
Los primeros los tienes en https://oeis.org/A002997:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841,
29341, 41041, 46657, 52633,…
Bastará recorrer los números coprimos con uno de ellos y
comprobar que es pseudoprimo con todos ellos.
Hay criterios más sencillos, que puedes consultar en
https://en.wikipedia.org/wiki/Carmichael_number.
Números
de Sarrus o Poulet
Estos son los pseudoprimos en base 2, también llamados
números de Sarrus, Poulet o simplemente psudoprimos, sin especificar el módulo.
El primer pseudoprimo módulo 2 es el 341, porque es
compuesto (341=11*31) y cumple que
2340 =1
(mod 341)
Esta condición se verifica fácilmente, ya que 210=1024=3*341+1
presenta resto 1 respecto al módulo 341, por lo que todas sus potencias, entre
ellas 2340 también tendrán ese mismo resto.
El segundo pseudoprimo módulo 2 es 561, que es compuesto
(561=3*11*17) y se verifica que
2560 =1
(mod 561)
La sucesión de números de Poulet la tienes en http://oeis.org/A001567
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701,
2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261,
10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705,
18721, 19951, 23001, 23377, 25761, 29341...
Aquí nos hemos limitado a presentar conceptos básicos y
facilitar la búsqueda de pseudoprimos. Se podría extender más su estudio, pero
superaría los objetivos de este blog.
