Cryptography Reference
In-Depth Information
integers that primes become less dense as the value increases:
2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 ,...
The question is whether there is still a reasonable chance that a random number
with, say, 512 bit, is a prime. Luckily, this is the case. The chance that a randomly
picked integer p is a prime follows from the famous prime number theorem and is
approximately 1 / ln( p ). In practice, we only test odd numbers so that the likelihood
doubles. Thus, the probability for a random odd number p to be prime is
2
ln( p ) .
P ( p is prime)
In order to get a better feeling for what this probability means for RSA primes, let's
look at an example:
Example 7.7. For RSA with a 1024-bit modulus n , the primes p and q each should
have a length of about 512 bits, i.e., p , q
2 512 . The probability that a random odd
number p is a prime is
2
ln(2 512 ) =
2
512 ln(2)
1
177 .
P ( p is prime)
This means that we expect to test 177 random numbers before we find one that is a
prime.
The likelihood of integers being primes decreases slowly, proportional to the bit
length of the integer. This means that even for very long RSA parameters, say with
4096 bit, the density of primes is still sufficiently high.
7.6.2 Primality Tests
The other step we have to do is to decide whether the randomly generated integers p
are primes. A first idea could be to factor the number in question. However, for the
numbers used in RSA, factorization is not possible since p and q are too large. (In
fact, we especially choose numbers that cannot be factored because factoring n is the
best known attack against RSA.) The situation is not hopeless, though. Remember
that we are not interested in the factorization of p . Instead we merely need the
statement whether the number being tested is a prime or not. It turns out that such
primality tests are computationally much easier than factorization. Examples for
primality tests are the Fermat test, the Miller-Rabin test or variants of them. We
introduce primality test algorithms in this section.
Practical primality tests behave somewhat unusually: if the integer p in question
is being fed into a primality test algorithm, the answer is either
 
Search WWH ::




Custom Search