Trouver un nombre premier supérieur à une borne donnée

Est un algorithme déterministe à temps polynomial connu pour le problème suivant:

Entrée: un nombre naturel (en encodage binaire) $n$

Sortie: un nombre premier . $p > n$

(Selon une liste de problèmes ouverts par Leonard Adleman, le problème était ouvert en 1995.)

cc.complexity-theory open-problem nt.number-theory polynomial-time primes Vincenzo
la source

+1: Cela m'a rappelé que le problème de décision naturel correspondant n'est pas le test de primalité (qui est dans ) mais plutôt le problème suivant: étant donné , y a-t-il un nombre premier dans l'intervalle ?

P

$\mathbf{P}$

a < b

$a<b$

[a, b]

$[a,b]$

Kaveh

@Kaveh: Trois doigts pointés vers moi, je suppose. Nous devrions mettre en place une politique interdisant les réponses dans les commentaires;)

Hsien-Chih Chang 張顯之

Réponses:

Le meilleur résultat inconditionnel actuel a été donné par Odlyzko, qui trouve un en temps . La forte conjecture du projet Polymath4 cherche à déterminer si cela peut être fait en temps polynomial, selon des hypothèses théoriques raisonnables comme le GRH. $p >N$ $O(N^{1/2 + o(1)})$

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

Actuellement, le projet cherche à répondre à la question suivante:

Étant donné un nombre et un intervalle entre et , vérifiez dans le temps pour certains si l'intervalle contient un nombre premier. $N$ $N$ $2N$ $O(N^{1/2 - c})$ $c>0$

Jusqu'à présent, ils ont une stratégie qui détermine la parité du nombre de nombres premiers dans l'intervalle.

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

Cong Han
la source

En supposant une conjecture standard dans la théorie des nombres, qui stipule que

Conjecture de Cramér : Soit le n-ième premier. Alors . $p_n$ $p_{n+1}-p_n = O(\log^2 p_n)$

Nous avons un algorithme déterministe en temps polynomial pour le problème, simplement en exécutant le test de primalité sur chaque nombre supérieur à partir de . (Bien sûr, devrait être assez grand; pour les petits nous les avons traités séparément.) $n$ $n+1$ $n$ $n$

Mais je ne suis pas sûr que cela puisse être prouvé sans condition.

Hsien-Chih Chang 張顯之
la source

Je suis curieux de savoir à quel point la conjecture de Cramér est standard. J'avais l'impression que les chances étaient contre.

Cong Han

@Cong: Je ne suis pas vraiment familier avec la conjecture, et mon impression est que nous avons des preuves dans les résultats numériques et aussi dans le modèle aléatoire. Y a-t-il une indication que la conjecture pourrait être fausse? Je devrais peut-être dire «fort» au lieu de «standard».

Hsien-Chih Chang 張顯之

@ Hsien-Chih: J'en sais très peu à ce sujet (à part quelques rumeurs et un intérêt passager pour les projets Polymath), mais cet article de Granville, lié depuis le wiki sur la conjecture, semble le suggérer: dartmouth.edu/~ chance / chance_news / for_chance_news / Riemann /…

Cong Han

@Cong: On dirait une bonne lecture, je vais la parcourir dans quelques jours!

Hsien-Chih Chang 張顯之