Algoritmo para construir primos

Question

¿Existen buenos algoritmos para construir un primo mayor que $n$ para un número arbitrario de $n$ ?

Existen algunos enfoques de fuerza bruta: por ejemplo, la factorización $n!+1$ . Sin embargo, estoy buscando algo significativamente más eficiente; preferiblemente, polinómico en $n$ .

Además, si alguien conoce una prueba que muestre un límite en la velocidad de dicho algoritmo (digamos, $n^4$ ), me gustaría saberlo.

EDIT: Parece que el polinomio en $\ln(n)$ tiene más sentido.

Answer 1

Polinomio en $n$ no es eficiente porque la longitud de la entrada (medida en bits) es $\log_2 n$ y así $n$ es exponencialmente grande en relación con su longitud de entrada.

Así que es fácil encontrar un número primo mayor que $n$ en tiempo polinómico en $n$ (por ejemplo, con la respuesta de Morón).

Si está interesado en un algoritmo determinista, el proyecto polymath le ofrece los resultados actuales conocidos.

Pero existe un algoritmo aleatorio con tiempo polinómico en $\log_2 n$ que le da un primo mayor que $n$ . Eliges un número al azar del conjunto $n, \ldots, 2n$ y comprobar este número con AKS o Prueba de primalidad de Miller Rabin . Con la teorema del número primo se puede demostrar que hay suficientes primos en el conjunto (para grandes $n$ ) y si se repite este algoritmo $O(\log_2 n)$ veces se encuentra un primo con alta probabilidad.

En este momento no puedo encontrar una referencia para una prueba detallada para el algoritmo aleatorio. Pero si te interesa puedo buscarla cuando tenga más tiempo.

Answer 2

Terence Tao ha creado un "proyecto polimático" que aborda exactamente su pregunta. Aquí está la página correspondiente:

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Contiene una lista de conjeturas, resultados parciales y referencias. Para resumirlo todo: Por el momento la respuesta a su pregunta es No.

Answer 3

Bueno, teóricamente hablando, hay un determinista $\mathcal{O}(n \log ^{12} n)$ algoritmo de tiempo.

Por el postulado de Bertrand, hay un primer $p$ garantizado para satisfacer $n \le p \lt2n$ . (En la práctica, debería dar con uno mucho antes que $2n$ debido al teorema de los números primos).

Utilice el programa de prueba de primalidad AKS para probar cada uno de los números del rango $[n, 2n)$ y encontrarás uno.

También puedes probar a tamizar, etc., como se sugiere en las respuestas a esta otra pregunta aquí: El menor primo mayor de 2000

Answer 4

Existe un algoritmo de complejidad $O((\ln n) \cdot P(n))$ donde $P(n)$ es la complejidad de calcular la función de recuento de primos en n (normalmente denotada como $\pi(n)$ ).

Por el postulado de Bertrand hay un primo en el intervalo $[n,2n]$ para que puedas hacer una búsqueda binaria en él:

Si $\pi\left(n+\frac{n}{2}\right)-\pi(n)$ > 1 hay un primo en el intervalo $\left[n, n+\frac{n}{2}\right]$ , de lo contrario hay un primo en el intervalo $\left[n+\frac{n}{2}+1,2n\right]$ y así se obtiene un intervalo más pequeño que contiene un primo. Repite el cálculo en el nuevo intervalo. El cálculo para saber cuál de los 2 intervalos utilizar necesita tiempo $O(P(n))$ . Como cada intervalo es la mitad del tamaño del anterior, el número total de cálculos necesarios es O(ln n).

El algoritmo de Odlyzko para $\pi(n)$ tiene complejidad $O(n^{\frac{1}{2}})$ . Hay un enlace a una breve descripción de la misma en la página del polímata. Así que la complejidad global de este algoritmo es $O((\ln n)n^{\frac{1}{2}})$ .