In several prime generation schemes I saw we pick a random number uniformly at random from a wide range and find the next prime after it.

Obviously with such a scheme some primes are more likely than others, a prime is as likely as the distance to the previous prime.

The question is how unbalanced is this? If a friendly alien gave me a list of the top X most likely primes from a much wider range how likely would a random prime from the scheme above be on the list?

  • $\begingroup$ Not an answer, but the density of primes is so high that it doesn't probably matter all that much for any large prime value (size >= 512 bits or so). $\endgroup$ – Maarten Bodewes Jan 21 at 12:06
  • $\begingroup$ I think the answer is hidden in the prime-gap. $\endgroup$ – Maarten Bodewes Jan 21 at 12:12
  • 1
    $\begingroup$ "Obviously with such a scheme some primes are more likely than others, a prime is as likely as the distance to the previous prime." How do you know that? Could you explain this further? $\endgroup$ – AleksanderRas Jan 21 at 14:48
  • 1
    $\begingroup$ @AleksanderRas consider a conceptual range [0,100] where there are two primes. the first in in the position 75 and second is in the 100. now generate numbers between 0 an 100. 75 of them will result in prime in position 75 and 25 of them will result in the prime in position 100. The primes distance is not regular. $\endgroup$ – kelalaka Jan 21 at 15:47
  • $\begingroup$ On second thought, if the total range of the top $X$ given as $x$ then the remaining $P-X$ can be quantized. We know the total range, we know the app. distribution of the primes. Ask the Oracle for more information. $\endgroup$ – kelalaka Jan 21 at 18:30

First some empirical results, over the first 1 million primes the to 0.1% will show up 0.65% of the time the top 1% will occur 4.7% of time and the top 10% will happen 29% of the time.

Looking at visual from https://en.wikipedia.org/wiki/Prime_gap gap distribution It doesn't look like it has a heavy tail and seems to decline super linearly. this suggest a small tail will never be a large portion.

For larger numbers the largest ratio between the prime gap and $ln(p)$ is 41 (This ratio is called merit), this is largest known and not an upper bound, but if we take it as an upper bound, and if we take ln(p) as the average distance and 2 as the minimum distance. The most extreme imbalance would be if all gaps were ever maximal or minimal (obviously not the case just for a bound). We mark the ratio of maximal gaps as r. So we will get $ln(p)=r * ln(p)*41+ 2*(1-r)$ which leads to $r=(ln(p)-2)/(41*ln(p)-2)$ for $p=2^{1024}$ this comes out 2.5%, and these would come up 99% of the time. But obviously we can't have many gaps of size 2. We can improve this somewhat but not much.

So we get a huge discrepancy between what we expect and we can prove. If we want a stronger claim then assuming maximal merit things get worse we can bound the gap to be no more than $p^{0.525}$ and if again assume to have a range where gaps are almost entirely either this maximum or very small, we will be able to get a more extreme ratio. Yet even this scenario won't get enough for e.g efficient factorization. If we have a range from $2^{1023}$ to $2^{1024}$ even with maximal gap there are still a lot of primes there. If we would try to factor with trial division we would get no more than a square root speed up over naive trial division which is not competitive with other methods.

| improve this answer | |
  • 1
    $\begingroup$ There's a folklore method to fight just the effect you are describing, and generate closer-to-uniform primes: to generate a $k$-bit prime, first pick a random $j$ near $k$ (say $k/2\le j<3k/2$), then an (odd) starting $p$. After testing that a candidate $p$ is not prime, move to $p+2j$ rather than $p+2$ as usual. When sieving for prime, we can space the sieve entries by $2j$ rather than $2$. $\endgroup$ – fgrieu Jan 23 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.