Cryptography Reference
In-Depth Information
x
ln
x
π(
)
Theorem 6.2
(The Prime Number Theorem, PNT)
x
is asymptotic to
(and
(
)
also to
li
x
).
Remark 6.1
The probabilistic interpretation of the PNT is the following: a random
integer, drawn uniformly from the interval
[
1
,
x
]
, will be prime with probability
asymptotic to 1
ln
x
. As a consequence, the expected number of draws required to
obtain a random prime from this interval is asymptotic to ln
x
.
/
Exercise 6.1
Use Maple to compute the exact value of the ratio between the number
of primes in the interval
10
8
-10
7
10
8
10
12
-10
7
10
12
]
and compare these values to the values predicted by the PNT in the two versions
given above. (Hint: Do not use
numtheory:-pi
which will be too slow but write
a procedure that uses
isprime
to count the number of primes in an interval instead.)
[
,
]
and the number of primes in
[
,
The following plot shows the amazing smoothness of
π(
x
)
when viewed from a
x
ln
x
distance and also how close the approximations by
are. Here we use
Maple's function
Li
which represents the 'Cauchy principal value' of the integral
and li
(
x
)
x
0
dt
ln
t
:
1
> plot([numtheory:-pi(floor(x)), x/ln(x), Li(x)], x = 2..10ˆ8, linestyle = [1, 7, 6],
color = [black, black, black], thickness = [0, 1, 3], font = [times, roman, 8],
axes = boxed, legend = [Pi(x), 'x/ln(x)', Li(x)], legendstyle = [location = top])
This produces the following plot:
L
in the range
plotted above is well below the square root of
x
. This fact is related to one of the
The magnitude of the error in the approximation of
π(
x
)
by Li
(
x
)
1
This is the so-called 'American' version of the logarithmic integral, while the 'European' version
li
)
=
2
dt
ln
t
is related to it by the formula li
045163780 (the
notations Li and li are usually interchanged but we use Li this way to conform to Maple's usage).
(
x
(
x
)
=
Li
(
x
)
−
Li
(
2
)
=
Li
(
x
)
−
1
.
