Cryptography Reference
In-Depth Information
6.1.1 Searching for Large Random Primes
The natural way of finding very large random primes is to choose, at random, integers
of the required size and submit them to a
primality test
, an algorithm that takes an
integer as input and produces a yes/no output that tells us whether the integer is
prime. The idea then would be to repeat this process until a prime is found but this
poses the following two problems:
1. Are there primality tests efficient enough to quickly determine whether an integer
of, say, 1024 bits, is prime? More precisely, are there polynomial-time primality
tests that are also efficient in practice?
2. Assuming that the answer to the preceding question is
yes
, how many times will
it be necessary to apply the primality test to random integers, on average, to find
a prime? Observe that if this number is polynomial in the size of the prime and
the answer to the first question is also positive, then we obtain a polynomial-time
algorithm to find a random prime.
It is often assumed that a positive answer to the first question is enough to solve
the problem of finding large primes but this is only a necessary condition and if the
problemfinally turns out to be easy it is also because the expected number of primality
tests to be performed is
low
(and indeed polynomial in the size of the prime) which
is an indirect way of saying that the primes are, in some sense, abundant among the
integers.
To better appreciate the importance of having a satisfactory answer to the second
question above, let us compare this problem to the similar one of finding a random
perfect square (an integer which is the square of another one) of 1024 bits. Of
course, this can easily be accomplished by just taking a suitable 512-bit integer and
squaring it. However, as the primes appear to be distributed pseudo-randomly among
the integers, we do not have a similar method for computing a prime from a random
integer with only one arithmetical operation so the meaningful experiment would be
the following one: assume that the primes are, on average, as dense as the squares
among the natural numbers or, equivalently, that our task were to find a 1024-bit
square by taking random integers of this size and submitting them to a 'squareness
test' that would check whether they are really squares. In the next example we carry
out this experiment with Maple.
Example 6.1
We build a Maple function to search for squares that proceeds by
first generating
k
-bit pseudo-random integers and then submitting them to Maple's
squareness test
issqr
that checks whether they are squares. As on other occasions
we insist that generating pseudo-random numbers is not a trivial matter for we need a
source of true randombits. For this demonstration, we are going to useMaple's default
pseudo-random algorithm with automatic seeding provided by the
randomize()
function; this is sufficient for our purposes here but, as we have repeatedly warned, it
is not a secure method for other cryptographic uses for several reasons: the generator
is not unpredictable and the automatic seeds are too small and far from random.
