Encontrar un primo mayor que un límite dado

25

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).

Vincenzo
fuente
1
+1: Me recordó que el problema de decisión natural correspondiente no es la prueba de primalidad (que está en ) sino el siguiente problema: dado a < b , ¿hay un número primo en el intervalo [ a , b ] ? Pa<b[a,b]
Kaveh
@Kaveh: Supongo que tres dedos apuntando hacia mí. Deberíamos establecer una política que prohíba las respuestas en los comentarios;)
Hsien-Chih Chang 張顯 之

Respuestas:

23

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>NO(N1/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.NN2NO(N1/2c)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/

Cong Han
fuente
14

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 ) .pnpn+1pn=O(log2pn)

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).nn+1nn

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

Hsien-Chih Chang 張顯 之
fuente
1
Tengo curiosidad por saber qué tan estándar es la conjetura de Cramér. Tenía la impresión de que las probabilidades estaban en contra.
Cong Han
@Cong: No estoy realmente familiarizado con la conjetura, y mi impresión es que tenemos evidencias en resultados numéricos y también se cumple en el modelo aleatorio. ¿Hay alguna indicación de que la conjetura podría ser falsa? Tal vez debería decir 'fuerte' en lugar de 'estándar'.
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Sé muy poco sobre esto (además de algunos rumores y un interés pasajero en los proyectos Polymath), pero este artículo de Granville, vinculado desde el wiki en la conjetura, parece sugerirlo: dartmouth.edu/~ chance / chance_news / for_chance_news / Riemann / ...
Cong Han
@Cong: Parece una buena lectura, ¡lo revisaré en unos días!
Hsien-Chih Chang 張顯 之