Cryptography Reference
In-Depth Information
at primes in large intervals we soon see a pattern emerge. The first mathematician to
do that was Gauss, who computed all the primes up to 3,000,000. We are going to do
a similar thing with larger intervals using Maple. Note that to choose a prime of, say,
1024bits, the relevant question related to problem 2 above is: what is the probability
that a random 1024-bit integer is prime? Following the steps of Gauss and with this
question in mind, we count the number of primes in a series of large intervals. For this
we use Maple's function
isprime
which is a probabilistic primality test (discussed
in more detail below) that always gives the correct answer (
true
) when the number
submitted to the test is prime and has a very low probability (which might even be
zero although some heuristic arguments suggest that this is not the case) of outputting
true
when the number is composite (so that, if the output of the function is
false
,
we have theoretical certainty that the number is composite). A quick computation
gives:
> map(nops, map(x -> select(isprime, x),
[seq(['$'((2ˆ64)ˆi-2ˆ15..(2ˆ64)ˆi)], 'in'(i, [1, 2, 4, 8, 16, 32]))]));
[720, 374, 178, 95, 45, 25]
This shows that if we consider intervals of length 2
15
centered at integers of
64
2048 bits, each time that the size of the numbers doubles, the den-
sity of primes in the interval is reduced by approximately half. Moreover, the relative
frequencies of primes in these intervals are close to the inverse of the logarithm of
the center of the interval as can easily be checked. Experimental data similar to these
(but with smaller numbers) led Gauss in 1792-1793 to conjecture that the probabil-
ity of a large random integer close to
n
being prime is about
,
128
,
256
,...,
1
ln
n
. Another way of
interpreting this is to look at the function
that counts the number of primes that
are less than or equal to a given positive integer
x
. The preceding conjecture suggests
the estimate:
π(
x
)
1
ln
n
.
π(
x
)
=
2
≤
n
≤
x
If we count the total number of integers from 2 to
x
, which is approximately equal
to
x
and we multiply it by the smallest of these probabilities which is
1
ln
x
, this leads
to the conjecture, made by Gauss and Legendre at the beginning of the nineteenth
century, that for
x
large,
x
ln
x
. It is intuitively obvious
(at least for those with a basic understanding of integration) that a more precise
approximation to
π(
x
)
is approximately equal to
π(
x
)
should be obtained by considering the 'logarithmic integral'
x
dt
ln
t
,
li
(
x
)
=
2
of which the preceding sum is a 'Riemann sum'. This was also conjectured by Gauss
and his conjecture may be formulated as follows. Recall that two functions with
positive real values,
f
and
g
, are asymptotic (denoted
f
(
x
)
∼
g
(
x
)
) whenever
f
(
x
)
lim
x
→∞
1. The conjecture of Gauss (and Legendre) about the distribution
of primes was eventually proven in 1896 by Hadamard and de la Vallée Poussin as
the following theorem (see [77] for a proof):
)
=
g
(
x
