Un pseudoprimo fuerte es un número compuesto que pasa la prueba de primalidad de Miller-Rabin . Todos los números primos pasan esta prueba, pero una pequeña fracción de los compuestos también la pasan, lo que los convierte en " pseudoprimos ".
A diferencia de los pseudoprimos de Fermat , para los cuales existen números que son pseudoprimos para todas las bases coprimos (los números de Carmichael ), no hay compuestos que sean pseudoprimos fuertes para todas las bases.
Digamos que queremos investigar si n = 31697 es un primo probable (PRP). Elegimos la base a = 3 y, inspirados en el pequeño teorema de Fermat , calculamos:
Esto muestra que 31697 es un PRP de Fermat (base 3), por lo que podemos sospechar que es un número primo. Ahora reducimos repetidamente el exponente a la mitad:
Las primeras veces no arrojan nada interesante (el resultado seguía siendo 1 módulo 31697), pero en el exponente 3962 vemos un resultado que no es ni 1 ni menos 1 (es decir, 31696) módulo 31697. Esto demuestra que 31697 es de hecho compuesto ( es igual a 29×1093). Módulo primo, el residuo 1 no puede tener otras raíces cuadradas que 1 y menos 1. Esto muestra que 31697 no es un pseudoprimo fuerte para la base 3.
Para otro ejemplo, elija n = 47197 y calcule de la misma manera:
En este caso el resultado sigue siendo 1 (mod 47197) hasta llegar a un exponente impar. En esta situación, decimos que 47197 es un primo probable fuerte para base 3. Debido a que resulta que este PRP es, de hecho, compuesto (se puede ver eligiendo otras bases además de 3), tenemos que 47197 es un pseudoprimo fuerte para base 3. .
Finalmente, considere n = 74593 donde obtenemos:
Aquí llegamos a menos 1 módulo 74593, una situación que es perfectamente posible con un número primo. Cuando esto ocurre, detenemos el cálculo (aunque el exponente aún no es impar) y decimos que 74593 es un primo probable fuerte (y, como resulta, un pseudoprimo fuerte) en base 3.
Un número compuesto impar n = d · 2 s + 1 donde d es impar se llama pseudoprimo fuerte (Fermat) en base a si:
o
(Si un número n satisface una de las condiciones anteriores y aún no sabemos si es primo, es más preciso referirnos a él como un primo probable fuerte con base a . Pero si sabemos que n no es primo, entonces podemos usar el término pseudoprimo fuerte.)
La definición se cumple trivialmente si a ≡ ±1 (mod n ), por lo que estas bases triviales a menudo se excluyen.
Guy da por error una definición que incluye solo la primera condición, que no todos los primos cumplen. [1]
Un pseudoprimo fuerte con base a es siempre un pseudoprimo de Euler-Jacobi , un pseudoprimo de Euler [2] y un pseudoprimo de Fermat con esa base, pero no todos los pseudoprimos de Euler y Fermat son pseudoprimos fuertes. Los números de Carmichael pueden ser pseudoprimos fuertes para algunas bases (por ejemplo, 561 es un pseudoprimo fuerte para la base 50), pero no para todas las bases.
Un número compuesto n es un pseudoprimo fuerte para como máximo una cuarta parte de todas las bases por debajo de n ; [3] [4] por lo tanto, no existen "números de Carmichael fuertes", números que sean pseudoprimos fuertes para todas las bases. Por lo tanto, dada una base aleatoria, la probabilidad de que un número sea un pseudoprimo fuerte con respecto a esa base es menor que 1/4, lo que forma la base de la prueba de primalidad de Miller-Rabin, ampliamente utilizada . La verdadera probabilidad de una falla es generalmente mucho menor. Paul Erdos y Carl Pomerance demostraron en 1986 que si un entero aleatorio n pasa la prueba de primalidad de Miller-Rabin a una base aleatoria b, entonces n es casi con seguridad un primo. [5] Por ejemplo, de los primeros 25.000.000.000 enteros positivos, hay 1.091.987.405 enteros que son probables primos de base 2, pero sólo 21.853 de ellos son pseudoprimos, y aún menos son pseudoprimos fuertes, ya que este último es un subconjunto de los anterior. [6] Sin embargo, Arnault [7] proporciona un número de Carmichael de 397 dígitos que es un pseudoprimo fuerte para cada base menor que 307. Una forma de reducir la posibilidad de que dicho número se declare erróneamente como probablemente primo es combinar un número primo probable fuerte. prueba con una prueba primaria probable de Lucas , como en la prueba de primalidad de Baillie-PSW .
Hay infinitos pseudoprimos fuertes para cualquier base. [2]
Los primeros pseudoprimos fuertes en base 2 son
Los primeros en llegar a la base 3 son
Los primeros en llegar a la base 5 son
Para base 4, consulte OEIS : A020230 , y para base 6 a 100, consulte OEIS : A020232 a OEIS : A020326 . Al probar las condiciones anteriores en varias bases, se obtienen pruebas de primalidad algo más potentes que si se utiliza una sola base. Por ejemplo, sólo hay 13 números menores que 25·10 9 que son pseudoprimos fuertes con las bases 2, 3 y 5 simultáneamente. Se enumeran en la Tabla 7 de. [2] El número más pequeño es 25326001. Esto significa que, si n es menor que 25326001 y n es un primo probable fuerte para las bases 2, 3 y 5, entonces n es primo.
Llevando esto más lejos, 3825123056546413051 es el número más pequeño que es un pseudoprimo fuerte para las 9 bases 2, 3, 5, 7, 11, 13, 17, 19 y 23. [8] [9] Entonces, si n es menor que 3825123056546413051 y n es un primo probable fuerte para estas 9 bases, entonces n es primo.
Mediante una elección juiciosa de bases que no sean necesariamente primas, se pueden construir pruebas aún mejores. Por ejemplo, no existe ningún compuesto que sea un pseudoprimo fuerte para las siete bases 2, 325, 9375, 28178, 450775, 9780504 y 1795265022. [10]
