. 2
( 2)

are probably prime with a controllably small chance of error.
Assume a test is set to fail once in 250tries. This means that there is a 1 in 10”
chance that the test falsely indicates that a composite number is prime. (The test
Page 259
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
11.5 Prime Number Generation

will never falsely indicate that a prime number is composite.) If for some reason you
need more confidence that the number is prime, you can set the failure level even
lower. On the other hand, if you consider that the odds of the number being com-
posite are 300 million times less than the odds of winning top prize in a state lot-
tery, you might not worry about it so much.
Overviews of recent developments in the field can be found in [ 1256,206]. Other
important papers are [ 1490,384,11,19,626,651,911].
Robert Solovay and Volker Strassen developed a probabilistic primality testing
algorithm [ 14901.Their algorithm uses the Jacobi symbol to test if p is prime:

(1) Choose a random number, a, less than p.
(2) If the gcd(u,p) f 1, then p fails the test and is composite.
(3) Calculate j = alp- 1™/2 mod p.
(4) Calculate the Jacobi symbol J(u,p).
(5) If j # J(u,p), then p is definitely not prime.
(6) If j = J(u,p), then the likelihood that p is not prime is no more than 50

A number a that does not indicate that p is definitely not prime is called a wit-
ness. If p is composite, the odds of a random u being a witness is no less than 50 per-
cent. Repeat this test t times, with t different random values for a. The odds of a
composite number passing ail t tests is no more than one in 2f.
Another, simpler, test was developed independently by Lehmann [945]. Here it
tests if p is prime:

(1) Choose a random number a less than p.
(2) Calculate u@ *JP- mod p.
(3) If alp- l)j2 + 1 or -1 (mod p), then p is definitely not prime.
(4) If &˜- “I2 = 1 or -1 (mod p), then the likelihood that p is not prime is no
more than 50 percent.

Again, the odds of a random a being a witness to p™s compositeness is no less than
50 percent. Repeat this test t times. If the calculation equals 1 or -1, but does not
always equal 1, then p is probably prime with an error rate of 1 in 2™.
The algorithm everyone uses-it™s easy-was developed by Michael Rabin, based
in part on Gary Miller™s ideas [ 1093,1284]. Actually, this is a simplified version of
the algorithm recommended in the DSS proposal [ 1149,1154].
Page 260
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER11 Mathematical Background

Choose a random number, p, to test. Calculate b, where b is the number of times
2 divides p - 1 (i.e., 2b is the largest power of 2 that divides p - 1). Then calculate m,
such that p = 1 + 2b*m.

(1) Choose a random number, a, such that a is less than p.
(2) Set j = 0 and set z = urn mod p.
(3) If z = 1, or if z = p - 1, then p passes the test and may be prime.
(4) If j > 0 and z = 1, then p is not prime.
(5) Setj=j+1.Ifj<bandz#p-1,setz=z2modpandgobacktostep(4).If
z = p - 1, then p passes the test and may be prime.
(6) If j = b and z zp - 1, then p is not prime.

The odds of a composite passing decreases faster with this test than with previous
ones. Three-quarters of the possible values of a are guaranteed to be witnesses. This
means that a composite number will slip through t tests no more than % of the time,
where t is the number of iterations. Actually, these numbers are very pessimistic.
For most random numbers, something like 99.9 percent of the possible a values are
witnesses [96].
There are even better estimations [417]. For n-bit candidate primes (where n is more
than loo), the odds of error in one test are less than 1 in 4n2(k/21™1™21. for a 256-bit
n, the odds of error in six tests are less than 1 in 251.More theory is in [418].
Practical Considerations
In real-world implementations, prime generation goes quickly.

(1) Generate a random n-bit number, p.
(2) Set the high-order and low-order bit to 1. (The high-order bit ensures that
the prime is of the required length and the low-order bit ensures that it
is odd.)
(3) Check to make sure p is not divisible by any small primes: 3, 5, 7, 11, and
so on. Many implementations test p for divisibility by all primes less than
256. The most efficient is to test for divisibility by all primes less than
2000 [949]. You can do this efficiently using a wheel [863].
(4) Perform the Rabin-Miller test for some random a. If p passes, generate
another random a and go through the test again. Choose a small value of u
to make the calculations go quicker. Do five tests [651]. (One might seem
like enough, but do five.) If p fails one of the tests, generate another p and
try again.

Another option is not to generate a random p each time, but to incrementally
search through numbers starting at a random point until you find a prime.
Step (3) is optional, but it is a good idea. Testing a random odd p to make sure it is
not divisible by 3, 5, and 7 eliminates 54 percent of the odd numbers before you get
Page 261
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
11.6 Discrete Logarithms in a Finite Field

to step (4). Testing against all primes less than 100 eliminates 76 percent of the odd
numbers; testing against all primes less than 256 eliminates 80 percent. In general,
the fraction of odd candidates that is not a multiple of any prime less than n is
1.12/m n. The larger the n you test up to, the more precomputation is required
before you get to the Rabin-Miller test.
One implementation of this method on a Spare II was able to find 256-bit primes
in an average of 2.8 seconds, 512-bit primes in an average of 24.0 seconds, 768-bit
primes in an average of 2.0 minutes, and 1024-bit primes in an average of 5.1 min-
utes [918].
Strong Primes
If n is the product of two primes, p and 4, it may be desirable to use strong primes
for p and q. These are prime numbers with certain properties that make the product
n difficult to factor by specific factoring methods. Among the properties suggested
have been [ 1328,651]:

The greatest common divisor of p - 1 and 4 - 1 should be small.
Both p - 1 and 4 - 1 should have large prime factors, respectively p™ and 4™.
Both p™ - 1 and q™- 1 should have large prime factors.
Both p + 1 and 4 + 1 should have large prime factors.
Both (p - 1)/2 and (4 - 1)/2 should be prime [182]. (Note that if this
condition is true, then so are the first two.)

Whether strong primes are necessary is a subject of debate. These properties were
designed to thwart some older factoring algorithms. However, the fastest factoring
algorithms have as good a chance of factoring numbers that meet these criteria as
they do of factoring numbers that do not [831].
I recommend against specifically generating strong primes. The length of the
primes is much more important than the structure. Moreover, structure may be
damaging because it is less random.
This may change. New factoring techniques may be developed that work better
on numbers with certain properties than on numbers without them. If so, strong
primes may be required once again. Check current theoretical mathematics journals
for updates.

Modular exponentiation is another one-way function used frequently in cryptogra-
phy. Evaluating this expression is easy:
ax mod n
The inverse problem of modular exponentiation is that of finding the discrete log-
arithm of a number. This is a hard problem:
Page 262
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER11 Mathematical Background

Find x where ax = b (mod n).
For example:
If3”= 15mod17,thenx=G
Not all discrete logarithms have solutions (remember, the only valid solutions are
integers). It™s easy to see that there is no solution, x, to the equation
3” = 7 (mod 13)
It™s far more difficult to solve these problems using 1024-bit numbers.
Calculating Discrete Logarithms in a Finite Group
There are three main groups whose discrete logarithms are of interest to cryp-

- The multiplicative group of prime fields: GF(p)
- The multiplicative group of finite fields of characteristic 2: GF(2”)
- Elliptic curve groups over finite fields F: EC(F)

The security of many public-key algorithms is based on the problem of finding
discrete logarithms, so the problem has been extensively studied. A good compre-
hensive overview of the problem, and the best solutions at the time, can be found in
[ 1189,1039]. The best current article on the topic is [934].
If p is the modulus and is prime, then the complexity of finding discrete logarithms
in GF(p) is essentially the same as factoring an integer n of about the same size, when
n is the product of two approximately equal-length primes [1378,934]. This is:
,I1 + O/l))[ln jp)]il/2l(ln (ln ipllllli2l

The number field sieve is faster, with an heuristic asymptotic time estimate of
e(1.923 + Oll))/ln (&˜3˜lln Iln ip11112/3)

Stephen Pohlig and Martin Hellman found a fast way of computing discrete loga-
rithms in GF(pJ if p - 1 has only small prime factors [1253]. For this reason, only
fields where p - 1 has at least one large factor are used in cryptography. Another
algorithm [ 141 computes discrete logarithms at a speed comparable to factoring; it
has been expanded to fields of the form GF(p”) [716]. This algorithm was criticized
[727] for having some theoretical problems. Other articles [ 15881show how difficult
the problem really is.
Computing discrete logarithms is closely related to factoring. If you can solve the
discrete logarithm problem, then you can factor. (The converse has never been
proven to be true.) Currently, there are three methods for calculating discrete loga-
rithms in a prime field [370,934,648]: the linear sieve, the Gaussian integer scheme,
and the number field sieve.
The preliminary, extensive computing has to be done only once per field. After-
ward, individual logarithms can be quickly calculated. This can be a security disad-
Page 263
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
11.6 Discrete Logarithms in a Finite Field

vantage for systems based on these fields. It is important that different applications
use different prime fields. Multiple users in the same application can use a common
field, though.
In the world of extension fields, GF(2”) hasn™t been ignored by researchers. An
algorithm was proposed in [727]. Coppersmith™s algorithm makes finding discrete
logarithms in fields such as GF(212™) reasonable and finding them in fields around
GF(2400) possible [368]. This was based on work in [180]. The precomputation stage
of this algorithm is enormous, but otherwise it is nice and efficient. A practical
implementation of a less efficient version of the same algorithm, after a seven-hour
precomputation period, found discrete logs in GF(2l”) in several seconds each
[ 1130,180]. (This particular field, once used in some cryptosystems [ 142,1631,1632],
is insecure.) For surveys of some of these results, consult [ 1189,1039].
More recently, the precomputations for GF(2227),GF(2313),and GF(2401)are done,
and significant progress has been made towards GF(2503).These calculations are
being executed on an nCube-2 massively parallel computer with 1024 processors
[649,650]. Computing discrete logarithms in GF(2593) still barely out of reach.
Like discrete logarithms in a prime field, the precomputation required to cal-
culate discrete logarithms in a polynomial field has to be done only once. Taher
ElGamal[520] gives an algorithm for calculating discrete logs in the field GF(p™).


. 2
( 2)