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].

Solovay-Strassen

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

percent.

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.

Lehmann

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™.

Rabin-Miller

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

And

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.

11.6 DISCRETE LOGARITHMS IN A FINITE FIELD

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-

tographers:

- 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.

is

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™).