Znalezienie liczby pierwszej większej niż podana granica

Jest deterministycznym algorytmem czasu wielomianowego znanym z następującego problemu:

Dane wejściowe: liczba naturalna (w kodowaniu binarnym)$n$

Wyjście: liczba pierwsza .$p > n$

(Według listy otwartych problemów Leonarda Adlemana problem był otwarty w 1995 r.)

Obecny najlepiej bezwarunkowy wynik podaje Odlyzko, która znajduje się doskonałą w O ( N 1 / 2 + O ( 1 ) ) razem. Silna hipoteza projektu Polymath4 ma na celu rozstrzygnięcie, czy można tego dokonać w czasie wielomianowym, przy rozsądnych założeniach teoretycznych, takich jak GRH.$p >N$$O(N^{1/2 + o(1)})$

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

Obecnie projekt stara się odpowiedzieć na następujące pytanie:

Biorąc pod uwagę liczbę oraz odstęp pomiędzy N a 2 N , sprawdzenie w czasie O ( N 1 / 2 - c ) od pewnego c > 0 , jeżeli przedział zawiera pierwszą.$N$$N$$2N$$O(N^{1/2 - c})$$c>0$

Jak dotąd mają strategię, która określa parzystość liczby liczb pierwszych w przedziale.

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

Zakładając standardowe przypuszczenie w teorii liczb, które to stwierdza

Cramera przypuszczenie : Niech jest n-tą pierwszą. Następnie p n + 1 - p n = O ( log 2 p n ) .$p_n$$p_{n+1}-p_n = O(\log^2 p_n)$

Mamy deterministyczny algorytm wielomianowego czasu dla problemu, po prostu uruchamiając test pierwszeństwa dla każdej liczby większej niż zaczynając od n + 1 . (Oczywiście n powinno być wystarczająco duże; dla małych n traktowaliśmy osobno.)$n$$n+1$$n$$n$

Ale nie jestem pewien, czy można to udowodnić bezwarunkowo.