Cryptography Reference
In-Depth Information
Millennium Prize Problems
[50], namely, the Riemann Hypothesis which, although
usually stated in terms of the
ζ
function (see [77]), is equivalent to:
x
2
+
ε
)
π(
x
)
=
Li
(
x
)
+
O
(
x
2
ln
x
for
ε>
0, and also to
π(
x
)
=
Li
(
x
)
+
O
(
)
(note that Li
(
x
)
and li
(
x
)
are
interchangeable in these asymptotic estimates).
Returning to the problem of finding large primes, the PNT now tells us what the
probability is that a random integer of a given size turns out to be prime. The PNT
entails that if this integer is close to
x
(where
x
is large), then this probability is
approximately equal to Li
x
. For example, if we want to choose a 1024-bit prime
at random, we may test odd integers only (further reductions are possible but we
shall not bother about this) and we know that, approximately, one in each
(
x
)/
> evalf(2ˆ1023/(2*(Li(2ˆ1024)-Li(2ˆ1023))));
354.7379025
of these odd integers (say, one in 355) will be prime. This makes it perfectly possible
in practice to find such a prime provided that we have an efficient primality test
at our disposal. In the next example we carry out an experiment similar to the one
in Example 6.1 but using primes instead of squares. For now we will use Maple's
probabilistic primality test
isprime
but we shall give an explicit alternative later
when discussing primality testing.
Example 6.2
From the previous discussion it follows that if we search for a prime
among, say, 2000 1024-bit integers, the expected number of primes found will be:
> 1000/(354.74);
2.818966003
To carry out this search we will use the previously defined function
Search
,
specifying that primes are to be searched for. The search method is thus the same as
the one we used for squares, only with
isprime
replacing
issqr
, but the results
are very different:
> Search(primes, 1024, 2000);
1559778344764876718654490785046718694117996300552855083961309795186209922144988460\
07438508179870434051861615971694915684935247430266032831535168292764641432481932\
56204997250068357648942911845765331170486636519191671310757984481205904856891278\
5491445393463982285807900238721649693476188960843975995549325273967
1221470048835205478008094528531016517664038704322845366170232503846629861702513191\
69062430828062297981841874787231042251793456302021355727000964932622431196208615\
12363764427793899802892968552257648513517268541023074167454296089177501037886749\
6802796430879354856259943925892203310400050217589414130412524323163
The preceding discussion implies that the expected number of odd integers that
should be tested in order to get a 1024-bit prime is approximately 355 (this is just
the expected value of the random variable that takes as its value the number of
independent tests which, as we have seen in Proposition 2.2, is 1
p
if
p
is the
probability that a random odd integer of this size passes the test). More generally,
from a complexity-theoretic point of view, the fact that the expected number of
/
