With a strong prime, there is no need to use generators, as Eric implied.

My wording here was a little clumsy; I was not contradicting Eric but rather attempting to amplify his comments. There is no need to look for primitive roots (elements of maximal order); rather you just want to avoid elements of low order. I found the paper I referred to which described the tradeoffs between the order of the group and the size of the modulus. It is "Efficient Signature Generation by Smart Cards", by C.P. Schnorr, in the Journal of Cryptology, 1991, v4, pp161-174. This is the patented Schnorr signature which has been the basis for PKP's claim that the federal Digital Signature Standard infringes the Schnorr patent. (Bruce Schneier recently posted on sci.crypt that a paper presented at Eurocrypt 94 analyzed all the different discrete- log based signature scheme, and in his opinion cast doubt on this claim of infringement.) Schnorr deals with a prime p, and a smaller prime q which divide p-1. In his system, q is a lot smaller than p, just big enough to provide the requisite security. Small q's allow for faster calculation of g^x since x is, say, 140 bits rather than 512 bits. Here is what Schnorr writes on page 163 (he uses "alpha" where we were using g, as the generator of the group): "The Security Complexity 2^t. We wish to choose the parameters p, q so that forging a signature or an authentication requires about 2^t steps by known methods. For this we choose q >= 2^(2t) and p such that 2^t is about exp(sqrt(ln p ln ln p)). The security number t may depend on the application intended. For signature we consider in particular t=72 rather that [sic] t=64, since 2^64 steps may be insufficient in view of the rapid technological progress in computing power and speed. For p>=2^512 and q>=2^140 the discrete logarithm problem requires at least 2^72 steps by known algorithms. (It may soon be necessary to increase the lower bound p>=2^512 due to the current progress in computing discrete logarithms.) The restriction that the order of [alpha] is a prime much smaller than p provides no advantage in any of the known discrete logarithm algorithms provided that q>=2^140. The prime q is necessary to avoid an index calculus attack and a square root attack (see Section 2)." The attack described in section 2 is interesting. Also known as the baby-step-giant-step attack, it is a simple meet-in-the-middle-technique. Suppose you wanted to solve a^x=y given a and y. Suppose for simplicity that x is known to be in the range of 0 to 100. What you can do is to calculate two lists. The first is ( a^10, a^20, a^30, ..., a^90 ). The second is ( y/(a^1), y/(a^2), y/(a^3), y/(a^4), ..., y/(a^9) ). Then you just look for a number which is common to both lists. If a^20 is the same as y/(a^4) then we know that y = a^24. So this takes square root of q in time and space. Schnorr says that Pollard has a trick to use less space. (Remember the discussion we had here some time back of the prac- ticality of meet-in-the-middle attacks given the huge space needs for even 2^64 hashes? I think Pollard's trick may apply to those as well.) Hal