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

25

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

Vincenzo
la source
1
+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 ? a < b [ a , b ]Pa<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:

23

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.O ( N 1 / deux + o ( 1 ) )p>NO(N1/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 2 N O ( N une / 2 - c ) c > 0NN2NO(N1/2c)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
14

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 + 1 - p n = O ( log 2 p n )pnpn+1pn=O(log2pn)

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 + 1 n nnn+1nn

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

Hsien-Chih Chang 張顯 之
la source
1
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 張顯 之