# What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath

(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

According to answers in this question.

Let $p$ be prime. Under GRH there exists prime $p' \equiv 1 \pmod{p}$ satisfying

$$p' \leq 70 p (\log p)^2 \qquad (1)$$

Doubling lemma Let $p$ be odd prime. In time polynomial in $\log{p}$ we can find prime $p' > 2p$.

From (1), the interval $[p+1,70 p (\log p)^2]$ contains about $70(\log{p})^2$ integers congruent to $1$ modulo $p$ of form $mp+1$ and at least one $p'$ is prime. Since $p+1$ is even, $p' \ge 2p+1$.

To find $p'$, enumerate the candidates and check them for primality.

The complexity is polynomial in $\log{p}$.

Start from $p=3$ and repeat Doubling lemma.

Each iteration produces prime at least twice larger than the previous step.

So this appears to give algorithm under GRH to find $p>k$ in time polynomial in $\log{k}$, which is equivalent to the Strong conjecture.

What is wrong with this?

• Even more stupid: given that one can test primality in polynomial time, and RH says there's a prime between $x$ and $x+O(log(x)^n)$ for some explicit $n$, what's wrong with just checking $10^k$ for primality, then $10^k+1$, $10^k+2$ etc until you succeed?
– eric
Sep 10 '15 at 9:23
• @Arul 70log(p)^2 is polynomial in log(p) by definition :). For small numbers the constants might be large. I didn't write "70p log(p)"
– joro
Sep 10 '15 at 9:26
• @Arul: aah I see. Thanks. But is this not a "standard conjecture in number theory"?? Cramer's conjecture or something?
– eric
Sep 10 '15 at 9:27
• @Arul Your are introducing a factor of $p$ which I didn't write. I meant there are $70(\log{p})^2$ candidates.
– joro
Sep 10 '15 at 9:27
• According to the links you gave, it appears the bound (1) you gave is based on a miscommunication or a typo, and has not actually been proved (even under GRH).
– zeb
Sep 10 '15 at 11:28

I have a somewhat different answer. The bound (1) is not known, but it is expected by some optimist paper. See for example this paper which says that one expects $p' = O(p (\log p)^2)$ and gives (page 1718) three references to papers discussing this. This estimate is way better that anything one can prove with GRH. If it holds, then there is nothing wrong with your algorithm, it works fine (and is nice, by the way).

However that estimate is so strong it is very doubtful. Actually it is related to Montgomery's conjecture, that $\psi(x,p,a) - x/(p-1) = O_\epsilon( (x/p)^{1/2+\epsilon} \log(x))$, where $\psi(x,p,a)$ counts the (weighted by their log) primes congruent to $a$ modulo $p$ up to $x$. If I'm not mistaken, this implies that the first such prime $p'$ is $O_\epsilon(p (\log p)^{2+\epsilon})$ which is very close to your estimate and enough for your algorithm. The problem is: Montgomery's conjecture has been proved false: see this article by Friedlander and Granville. As a replacement, the same authors proposes (conjecture 1) $\psi(x,p,a) - x/(p-1) = O_\epsilon( (x/p)^{1/2} x^\epsilon)$. This gives an estimate of $p'$ in $O(x^{1+\epsilon})$ and kills your algorithm.

So in conclusion, your algorithm works assume your estimate, but this estimate, while it has been conjectured, is at best very doubtful.

• Hi Joël, The conjecture, which is an analog of Cramer's conjecture, is of course wildly optimistic, but I think is believed to be true. The Friedlander-Granville work disproves Montgomery's conjecture by a Maier-type method, but it is still reasonable that $\psi(x;q,a) \gg \psi(x)/\phi(q)$ in a uniform range as in the Montgomery conjecture. Same story with primes in short intervals: the asymptotic formula fails for any short interval of size $(\log x)^A$ for any $A$, but still if $A>2$ we would expect a good number of primes in such intervals. Sep 11 '15 at 4:37
• Thanks. Just to clarify, this is not my estimate, I cited source.
– joro
Sep 11 '15 at 5:08
• Hi Lucia. The phenomenon you suggest is very interesting. I'd like to have a better understanding of what is to be expected in this mysterious world of conjecture that lie way behind GRH. (One or two years ago, I grew very skeptical of that conjecture O(p (log p)^2) and made a lot of numerical tests, but it seemed to be true after all.)
– Joël
Sep 11 '15 at 14:51

The bound (1) is not known. Instead, $p'<(p\log p)^2$ is known by the work of Lamzouri-Li-Soundararajan.