El algoritmo de Mathematica utiliza para sus PrimeQ función se describe en MathWorld. La página web dice PrimeQ utiliza, "las múltiples Rabin-Miller de la prueba en las bases 2 y 3 combinado con un Lucas pseudoprime prueba". También dice:
"A partir de 1997, este procedimiento es conocido por ser correcta para todos $n<10^{16}$, pero no hay contraejemplos son conocidos y si existe alguna, que se espera que ocurren con probabilidad muy pequeña (es decir, mucho a menos que la probabilidad de un error de hardware en un equipo que realiza de la prueba)."
Más detalles sobre el algoritmo se dan en Un Curso Computacional de la Teoría de los números por David Bressoud. Ese libro dice que hay 52,593 enteros menos de $10^{16}$ que son 2 - y 3 - fuerte pseudoprimes. También sugiere Lucas pseudoprimes menos de $10^{16}$ son raros. La teoría de números es una muy rigurosa campo. Tiene un trabajo riguroso ha hecho para justificar la afirmación anterior de que, si un PrimeQ contraejemplos existen, se espera que ocurren con probabilidad muy pequeña. Todo lo que puedo encontrar, hasta ahora, es una extrapolación de la tendencia for ($n<10^{16}$), y que es muy de la mano-ondulado argumento.
Además de eso, soy consciente de ningún esfuerzo para extender la fuerza bruta de las pruebas de más de $10^{16}$. Con la ley de Moore y 15 años de trabajo, un progreso considerable que se podría haber hecho de esa manera.
