Los pseudoprimos

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

 a^j(m) =1 (mod m)

para todo a primo con m. (Teorema de Euler)

Si m es primo, la igualdad anterior se puede expresar como

a^m-1 =1 (mod m)

 (Pequeño Teorema de Fermat)

El recíproco no es cierto. Si para un a primo con m se cumple

a^m-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

 Por ejemplo, el resto de 3^26 respecto al módulo 7 sería RESTOPOT(3;26;7)=2, como puedes comprobar en la hoja potenciales.xls presentada más arriba:

 

Con esta función podemos averiguar si a^m-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 b^m-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

2³⁴⁰ =1 (mod 341)

Esta condición se verifica fácilmente, ya que 2¹⁰=1024=3*341+1 presenta resto 1 respecto al módulo 341, por lo que todas sus potencias, entre ellas 2³⁴⁰ 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

2⁵⁶⁰ =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.