Predecir si $n^2 + 1$ es primo

Question

Estoy tratando de escribir un programa que pueda decir si $n^2+1$ es primo donde n está en los números naturales (lo siento, no sé cómo escribir esto en notación matemática adecuada). Claro, puedo tomar un enfoque de fuerza bruta para comprobar si el número es primo, pero quiero comprobar millones de valores de n, así que como n se hace grande, $n^2$ se me va de las manos rápidamente y mi computación se ralentiza. ¿Hay algún método más eficiente para comprobar si es primo?

Answer 1

Un test de primalidad probabilístico muy rápido es el Prueba de Miller-Rabin .

Aquí hay una ejemplo de trabajo en línea de la prueba de Miller-Rabin que le ayudará a apreciar la velocidad de la prueba de primalidad utilizando este algoritmo.

También puedes instalar PARI/GP y ejecutar algo así:

for (n=1,1000000,if(isprime(n^2+1),print(n)))

Es increíblemente rápido; probando un millón de valores de $n$ tarda menos de un minuto. PARI/GP se basa (en parte) en la prueba de Miller-Rabin para comprobar la primalidad.

Nota: En algunas condiciones, la prueba de Miller-Rabin puede funcionar como determinista prueba de primalidad (es decir, le dará una respuesta garantizada si el número de entrada es primo o compuesto). Véase, por ejemplo Secuencia OEIS A014233 : números Impares más pequeños para los que la prueba de Miller-Rabin en las bases $\le n$ -el quinto primo no revela la composición . Esencialmente, la OEIS A014233 le da un límite por debajo del cual puede utilizar la prueba de Miller-Rabin de forma determinista. Por ejemplo, si ejecuta la prueba para cada parámetro "base" primo hasta 41, entonces la prueba determinará correctamente la primalidad de cualquier número de entrada impar hasta 3317044064679887385961981.