I am interested in (roughly estimating) how many random integers do I have to check before I find a prime of size say $100$ digits.

I was thinking like so:

Let the number of primes up to $X$ be denoted by $\pi(X)$. The famous Prime Number Theorem says that $$ \lim_{X\to\infty}\frac{\pi(X)}{X/\ln(X)}=1 $$ so a randomly chosen number $N$ has probability $$ P(N \ being \ prime)=\frac{1}{\ln(N)} $$ of being prime.

Now I need numbers of size $10^{100}$ which means I have $$ \frac{1}{\ln(10^{100})}=\frac{1}{100}\cdot \frac{1}{\ln(10)}\approx 0,02305 $$

so the chance of picking a prime is roughly $2,3\%$ therefore I need (in theory) to check at least $50$ numbers before I hit a prime.

Is my reasoning correct?

Thank you!


I made a silly calculator mistake the correct value is: $$ \frac{1}{230}\approx 0,00434 $$ so I need to check a bit over $200$ numbers say $250$.

  • 1
    $\begingroup$ You are not going to bother checking even numbers, are you? $\endgroup$ May 1 '18 at 6:05
  • 2
    $\begingroup$ The numerical value is not correct. It is about $\frac{1}{230}$. Of course, with trial division (lets say upto $100$) , you can speed up the search and you increase the chance to find a prime by a factor of $8.3$ if you try large numbers.. Basically , your approach is correct however. $\endgroup$
    – Peter
    May 1 '18 at 6:05
  • $\begingroup$ No definitely not, in a realistic case (further non ending with 5 etc) :) But the question said "random integers" so I assume they mean actually a randomly picked integer $\endgroup$ May 1 '18 at 6:06
  • $\begingroup$ @Peter thank you. I corrected the question. I made a silly calculator mistake $\endgroup$ May 1 '18 at 6:12
  • $\begingroup$ I have recently read that this approach (probability $\frac{1}{\ln(N)}$) has been refuted, but this should not be critical. I do not think that the error is big. $\endgroup$
    – Peter
    May 1 '18 at 6:19

There was a Polymath Project (see link here) to come up with an efficient deterministic algorithm to find a prime larger than a given number $N$ (equivalent to a prime of size at least $\lceil \log_2 N \rceil$ bits in your notation). Terence Tao led this effort and a paper (see abstract here) was published at the end of the project.

See also Terence Tao's blog here for a discussion of the results of the project.

I quote from the introduction of the paper, which confirms your guess of the randomized complexity, as being essentially $O(\log^{O(1)}N)$:

Note that if one allows probabilistic algorithms [..] one can accomplish this in time polynomial in the length of $N$ (i.e. in time at most $\log^{O(1)} N$); indeed, one can select integers in [N, 2N] at random and test each one for primality. [..] Using algorithms such as the AKS algorithm, each such integer can be tested in time at most $\log^{O(1)} N$, and by the prime number theorem one has about a $1/ \log N$ chance of success with each attempt, so the algorithm will succeed with (say) 99% certainty after at most $\log^{O(1)} N$ units of time

Note: The notation $\log^c N$ is used for $(\log N)^c$ here. AKS (Agarwal-Kayal-Saxena) algorithm which is used in the paper is a deterministic primality test with original complexity $O(\log^6 N)$ for a number of bitsize $N$, and it's since been improved to $O(\log^3 N)$ later. If this algorithm states that a number is prime, the number is indeed a prime, not subject to errors.


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.