Finden einer Primzahl, die größer als eine gegebene Schranke ist

Ist ein deterministischer Polynom-Zeit-Algorithmus für das folgende Problem bekannt:

Eingabe: eine natürliche Zahl (in binärer Kodierung)$n$

Ausgabe: eine Primzahl .$p > n$

(Laut einer Liste offener Probleme von Leonard Adleman war das Problem 1995 offen.)

Das derzeit beste unbedingte Ergebnis wurde durch Odlyzko gegeben, die ein erstklassiges findet in O ( N 1 / 2 + o ( 1 ) ) Zeit. Die starke Vermutung im Polymath4-Projekt versucht zu klären, ob dies in polynomialer Zeit unter vernünftigen zahlentheoretischen Annahmen wie der GRH möglich ist.$p >N$$O(N^{1/2 + o(1)})$

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

Derzeit versucht das Projekt die folgende Frage zu beantworten:

Bei einer Anzahl und einen Abstand zwischen N und 2 N , Check - in Zeit O ( N 1 / 2 - c ) für einig c > 0 , wenn das Intervall eine Primzahl enthält.$N$$N$$2N$$O(N^{1/2 - c})$$c>0$

Bisher haben sie eine Strategie, die die Parität der Anzahl der Primzahlen im Intervall bestimmt.

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

Unter der Annahme einer Standardvermutung in der Zahlentheorie, in der es heißt

Cramer's Vermutung : Sei die n-te Primzahl. Dann ist p n + 1 - p n = O ( log 2 p n ) .$p_n$$p_{n+1}-p_n = O(\log^2 p_n)$

Wir haben einen deterministischen Polynom-Zeit-Algorithmus für das Problem, indem wir einfach einen Primalitätstest für jede Zahl ausführen, die größer als beginnend mit n + 1 . (Natürlich sollte n groß genug sein; für kleine n haben wir es separat behandelt.)$n$$n+1$$n$$n$

Ich bin mir aber nicht sicher, ob dies unbedingt bewiesen werden kann.