Pseudoprimos
w-fuertesMiguel A. Trejo Malfaz
Universidad de Valladolid
Resumen:
Los números primos son bloques básicos con los que se forman, por multiplicación, todos los demás números naturales. De esta forma, dado un
número natural puede interesar conocer su carácter de primalidad. Para ello se hace necesario la creación de algoritmos eficientes que permitan decidir si un número es primo o no lo es. Tales algoritmos son conocidos como test de primalidad. Un primer ejemplo es el Pequeño Teorema de Fermat (P.T.F.), que permite conocer si un número es compuesto probando con distintas bases.
El recíproco de P.T.F. no es cierto. A los números
n compuestos que verifican la ecuación an-1 ≡ mód n se les denomina pseudoprimos en base a. Distintas concepciones de pseudoprimos (Euler, fuertes), permiten la creación de test de primalidad (Solovay-Strassen, Miller-Rabin). Nuestro objetivo será introducir dichos conceptos y exponer una generalización de pseudoprimos fuertes.