> Anyway -- suppose that in some group, you know that a^n=b, where a > and b are members of the group, and n is an integer. a^n indicates > the group operation iterated n times. The discrete log problem is > recovering n, given ``a'' and a^n=b. > > In some groups, this is a very hard problem. The group most commonl y > used in cryptography is the field GF(p), i.e., the field of integers > modulo p, where p is some large number, preferably a prime, and ``a' ' If I understand this correctly, if p is not a prime, then n may not be unique. Well, n isn't unique even if p is prime. Consider a=10,p=11. 10^2=10^4=10^6=10^8=10^10=1 mod 11. You only get a maximum-length cycle if ``a'' is a primitive root, hence the restriction I stated in the part I deleted... It doesn't matter that n isn't unique, though you do want a good distribution. Primitive roots have a maximal distribution, which is why they're good. But a reduction by, say, a factor of 2 doesn't matter in practice. (For p=11, try a=3.) The implementation of secure RPC in SunOS uses Diffie-Hellman (which relies on the difficulty of the discrete log problem) with base that's not a primitive root. To be sure, their key exchange was cryptanalyzed, but that's because they picked a 192-bit modulus, not because of the exponentiation base. If I recall correctly, if p=kq+1, for q a prime and k a small integer, there are (q-1)/k primitive roots in GF(p). That suggests generating p=2q+1, p and q prime, which gives a very good density. And checking if a number is a primitive root is easy (again, to my recollection; I'm not a number theorist) if you know the factorization of p-1, which of course we do in this case.