Número pseudoprimo fuerte

Supóngase que se quiere investigar si n = 31697 es un probable primo (PRP).Para otro ejemplo, elíjase n = 47197 y calcúlese de la misma manera: En este caso, el resultado sigue siendo 1 (mod 47197) hasta llegar a un exponente impar.En esta situación, se dice que 47197 es un primo probable fuerte de base 3.Cuando esto ocurre, se detiene el cálculo (aunque el exponente aún no es impar) y se dice que 74593 es un primo probable fuerte (y, como resultado, un pseudoprimo fuerte) en base 3.Guy dio erróneamente una definición con solo la primera condición, que no todos los números primos cumplen.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]​ y por lo tanto, no hay números de Carmichael fuertes, números que son pseudoprimos fuertes para todas las bases.Paul Erdős y Carl Pomerance demostraron en 1986 que si un entero aleatorio n pasa la prueba de primalidad de Miller-Rabin respecto a una base aleatoria b, entonces n es casi seguramente un primo.Mediante la elección juiciosa de bases que no son necesariamente primas, se pueden construir pruebas aún mejores.