From: 7CF5048D@nowhere
Date: Mon, 5 Sep 94 14:50:21 PDT
To: sci.math.usenet@decwrl.dec.com
Subject: How to find a primitive root of unity, for Diffe-Hellman?
Message-ID: <199409052037.AA04009@xtropia>
MIME-Version: 1.0
Content-Type: text/plain



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