Cryptography Reference
In-Depth Information
One can try to understand how small this probability is by bearing in mind the
current estimates that the number of atoms in the observable universe is close to
10
80
...
As the preceding experiment shows, in order to be able to find large primes for
cryptographic use, it is necessary that they are much denser than squares. Fortunately,
it turns out that this is indeed the case and to appreciate it, let us have a look at the
distribution of primes.
6.1.2 The Distribution of Prime Numbers
The first important thing about the distribution of the primes was already known by
Euclid (it is Proposition 20 in topic IX of the
Elements
):
Theorem 6.1
The set of primes is infinite.
Proof
Assume, on the contrary, that the set of primes is finite, say
{
p
1
,...,
p
k
}
.
+
i
=
1
p
i
has, by Theorem 2.2 a prime factor
p
. Since
n
Then
n
=
1
≡
0
(
mod
p
)
but
n
≡
1
(
mod
p
i
)
for all
i
=
1
,...,
k
, we see that
p
does not belong to the set
{
p
1
,...,
p
k
}
, which is a contradiction and completes the proof.
The fact that the set of primes is infinite does not mean that the primes are so
abundant as to make them easy to find. The squares also form an infinite set and we
have seen that they are not easy to find by choosing numbers at random and testing
whether they are squares. An indirect way to see that squares are much less abundant
than primes is to compute the sum of the series defined by their inverses, something
that was already known to Euler and that Maple also knows:
> sum(1/xˆ2, x=1..infinity);
6
π
2
Now, what happens if we do the same with the inverses of the primes? The series
p
prime
1
p
is divergent as Euler showed (in a non-rigorous way) already in 1737.
Using Maple's function
ithprime
we can compute the sum of the inverses of the
first million primes as follows:
> evalf(add(1/ithprime(i), i=1..1000000));
3.068219048
It is estimated that the sum of the inverses of all the primes computed so far is
about 4 and is not going to increase significantly in the near future since the series
diverges very slowly. Anyway, this shows that primes are much more abundant than
squares and fosters hopes that it will be easy to find large primes. But this does not
give a very precise idea about
how
the primes are distributed. Looking at primes
in short intervals it is easy to appreciate that their distribution is very irregular; for
example, given a prime it is very difficult to predict where the next prime will be: it
can be just two positions away or it can be much further away. However, if we look
