4

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!

Edit:

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$.

Vinyl_cape_jawa
  • 4,794
  • 1
    You are not going to bother checking even numbers, are you? – Angina Seng May 01 '18 at 06:05
  • 2
    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. – Peter May 01 '18 at 06:05
  • 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 – Vinyl_cape_jawa May 01 '18 at 06:06
  • @Peter thank you. I corrected the question. I made a silly calculator mistake – Vinyl_cape_jawa May 01 '18 at 06:12
  • 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. – Peter May 01 '18 at 06:19
  • Your calculation is correct. However, as is pointed out above, picking and testing random numbers is a very inefficient way of finding primes. – gandalf61 May 23 '18 at 08:18

1 Answers1

1

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.

kodlu
  • 9,338