-----BEGIN PGP SIGNED MESSAGE-----
How do I choose constants suitable for Diffe-Hellman? According to _Applied Cryptography_ n should be prime, also (n-1)/2 should also be prime. g should be a primitive root of unity mod n. n should be 512 or 1024 bits long. Are there any other requirements?
How can I choose such numbers? Are such numbers published anywhere?
Ok let me take a stab at finding g assuming n has been choosen to meet the above requirements. (I hope my math is still good.) Let Zn be the field defined by the prime n. Let G be the multiplicitive group defined in Zn. So |G| = n-1. Now n is large so 1 is not equal to -1 in Zn. Let N be { 1, -1} in G. It is a subgroup. Zn is abielian so it is Normal. We can consider the canoical map: G ---> G/N The order of G/N will be (n - 1)/2 which we are assuming to be prime. G/N is a cyclic group with no non trivial subgroups. Every element not = 1 is a generator. Pulling back to G we find that if g is not a root of unity, then the other member of its co-set = -g is! So take any g and raise to (n-1)/2 power. The result will be equal to 1 or -1. g raised to any lower power will not be equal to 1 or -1. Since (n-1)/2 is a large prime, it is odd. So if g to the (n-1)/2 is = to 1, then - -g to the (n-1)/2 = -1. So we can find a g which raised to the order (n-1)/2 power is = to -1. So g to the (n-1) power is =1 and g is a primitive root of unity. Have I made any errors? Did I get it right? -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAgUBLmt8dw2Gnhl89QSNAQHzmAP9GUGAmFcbgMyWxKtrzEvQYJS33FXGoGmr w4rXblv14lkwJX32hpoRKmicm3bdND2OPGgmM4EefGYggj+iCI+NU+l6II+MxhjY C4Rk3Xjn59H81FhNdfcNqOU9AirjwMBSqKzYtNCfbedB6HuQDCTeLSU5pjI5PSEQ wvFP7F3i5rY= =0r8J -----END PGP SIGNATURE-----