Encontrar un primo mayor que un límite dado

Es un algoritmo determinista de tiempo polinómico conocido para el siguiente problema:

Entrada: un número natural (en codificación binaria)$n$

Salida: un número primo .$p > n$

(Según una lista de problemas abiertos de Leonard Adleman, el problema se abrió en 1995).

El mejor resultado incondicional actual fue dada por Odlyzko, que encuentra un primer en O ( N 1 / 2 + O ( 1 ) ) tiempo. La fuerte conjetura en el proyecto Polymath4 busca resolver si esto se puede hacer en tiempo polinómico, bajo suposiciones teóricas de números razonables como el GRH.$p >N$$O(N^{1/2 + o(1)})$

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

Actualmente el proyecto busca responder la siguiente pregunta:

Dado un número y un intervalo entre N y 2 N , registro en el tiempo O ( N 1 / 2 - c ) para algunos c > 0 si el intervalo contiene un primo.$N$$N$$2N$$O(N^{1/2 - c})$$c>0$

Hasta ahora, tienen una estrategia que determina la paridad del número de primos en el intervalo.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/

Suponiendo una conjetura estándar en la teoría de números, que establece que

Conjetura de Cramér : Sea la enésima prima. Entonces p n + 1 - p n = O ( log 2 p n ) .$p_n$$p_{n+1}-p_n = O(\log^2 p_n)$

Tenemos un algoritmo determinista de tiempo polinómico para el problema, simplemente ejecutando la prueba de primalidad en cada número mayor que comience desde n + 1 . (Por supuesto, n debería ser lo suficientemente grande; para n pequeña tratamos por separado).$n$$n+1$$n$$n$

Pero no estoy seguro de que esto se pueda probar incondicionalmente.