Cryptography Reference
In-Depth Information
(
)
random (odd) integers to be tested in order to find a random prime near
n
is
O
ln
n
(
(
))
means that if we have a deterministic primality test of complexity
O
(where
f
is some function), then the algorithm to find the random prime (by picking integers
of the required size at random and submitting them to the primality test until a prime
is found) would be a Las Vegas algorithm with expected running time equal to
O
f
ln
n
. We shall return to this question after we discuss primality testing
and we will see that, although a polynomial-time deterministic primality test exists,
a much more efficient algorithm for finding random primes exists if we also allow
the primality test to be probabilistic.
(
f
(
ln
n
)
ln
n
)
Exercise 6.2
An alternative method which is often proposed to search for large
primes consists of choosing at random an integer of the appropriate size and then
looking for the next prime (for which Maple has the built-in function
nextprime
).
(i) Explain why this method does not choose primes uniformly at random.
(ii) Suppose that we use this method to choose a 1027-bit prime. Show that the
prime
p = 829941989940592799681292290602624775771923191122802210343305520413604881789386\
668418471359893967687633734762986527049578799912769146684379554452260666406153\
850673539530720664117262802108324083361812055783159794496017908673406145849102\
955238323521611423148927423872014310829119220858348387997402386170556695883
ity of being chosen by this method that is 8475 times higher than the probability
of the prime
q = 829941989940592799681292290602624775771923191122802210343305520413604881789386\
668418471359893967687633734762986527049578799912769146684379554452260666406153\
850673539530720664117262802108324083361812055783159794496017908673406145849102\
955238323521611423148927423872014310829119220858348387997402386170557282853
being chosen. Use Maple to compute both probabilities.
(iii) Write a Maple program to choose primes by this method and use it to obtain
a large sample of 1024-bit primes. Compare the average length of the gaps
2
preceding the primes in this sample with the average length of the gaps corre-
sponding to a sample of the same size in which the 1024-bit primes are chosen
by taking random 1024-bit integers and testing them with
isprime
.Givean
explanation for the difference between these values.
6.1.2.1 Extensions of the PNT and the Riemann Hypothesis
Euclid's theorem on the infinitude of the primes and the PNT have generalizations to
the primes in a congruence class modulo an integer
n
or, equivalently in an arithmetic
progression (this is just another name for a residue class) with common difference
n
. The natural question is: which residue classes
a
mod
n
contain primes and how
2
The term
prime gap
refers to the difference between two consecutive primes.
