Conference rusure::math

     If G is a generator for the prime p, then
     
           p-1
          G    = 1 (mod p)
     
     and
     
           (p-1)/q
          G        not= 1 (mod p)   for every prime q dividing p-1
     
     Conversely, if both conditions are satisfied then G is a
     generator.
     
     Actually, the first condition is true for every G not
     divisible by p.
     
     Is there a similar test for finite fields of size a power of p?
     
     Dan

Re: -.1

	If N = p^a where p is prime, then there exists a unique field
of order N.   If N is not a prime power, there is no field of that order.
Let's call these fields GF(p^a) cos everyone else does.

>	Does anyone know how to determine if a number is a "generator" 
>in a finite field?   In other words, how do I determine if a randomly 
>picked candidate for G results in a 1-to-1 mapping between x and Y in 
>the following equation?
>
>                    Y = G^x mod p  where p is a prime

	Replace that by:

		�(G): x --> G^x

where the domain is {0,...,(p^a)-2}
and the range is GF(p^a) \ {0}.

then the question is: how do I know for a given G if �(G) is a bijection?

	Actually, that's easier than coming up with a plausible G in the
first place.   When you *have* a G, then if a=1, you can check to see whether
it is square by the standard quadratic reciprocity relations you mentioned.
I don't know of how to check for other primes q such that q|(p-1), and
G = H^q.   But often taking powers of G is a reasonably cost-effective thing
to do.

>One text states the square root of G (mod p) must not exist and that 
>there are (p-1)/2 possible values for the generator.  Stated more 
>formally, G must not be a quadratic residue (mod p) or G's Legendre 
>symbol must be -1.  

	The multiplicative group for GF(p) is cyclic, and so has (p-1)/2
elements of odd order (assuming p <> 2).    As you note, these are not
necessarily generators.

>This appears to be true, but only if (p-1) is the
>product of [distinct] primes.  

	No, take GF(7).   The multiplicative group is C6, which has two
generators, 3 and 5.   If p-1 is product(i)((q_i)^(b_i)) where the q_i
are distinct primes, then the number of generators will be:

	product(i)((q_i - 1)(q_i)^(b_i - 1))

>If the factorization of (p-1) contains powers of
>primes, then additional candidates fail to be generators, but why?  

	Just think of the multiplicative group of order p-1.   Forget
about the field structure.   Finite fields are very easy, as long as you
just have to consider the additive properties or the multiplicative ones.
It's the combination that's tricky.

>What is the test for these?

	Dunno, but checking all the relevant powers of G to see whether
1 is reached has got to be one solution, apart from the quadratic stuff.

	I repeat, the tricky stuff is identifying plausible candidates for
the generators.

	I hope this is slightly helpful.   What's your problem?

Andrew.

>     Is there a similar test for finite fields of size a power of p?

	Yes, because all finite fields have cyclic multiplicative group.

            (p-1)/q
          G         <> I in GF(p^a)   for every prime q dividing (p^a)-1
     
     Conversely, if condition is satisfied then G is a generator.
     
(Once again, Deramo and I input replies at the same time.   Twin hounds
of truth, our flanks brush as we urgently quest the quarry.)

Time for bed, yawn.

Andrew

Thanks for the replies.  I ran some examples and the algorithm in .1
worked just fine.  Of course, the numbers were small enough that I could 
factor p-1 by inspection.

Given that the prime is probably quite large (255-1000 bits, depending 
on the location [U.S. vs. elsewhere] and export situation), does any one
have any good ideas on how to avoid factoring p-1?  How about building
the modulus from the product of some primes plus 1 and testing it for
primality? 

Since one of you asked what I wanted this for, I am considering using 
the Diffie-Hellman public key exchange for authentication on a large 
network application within DEC.  The request is really work-related, but 
D-H is only a candidate being considered at this point. D-H is based on
exponentiation of a generator modulo a prime and none of the literature
I could find gave me a good method for finding the generator. 

thanks again, doug

>     Is there a similar test for finite fields of size a power of p?

>>	Yes, because all finite fields have cyclic multiplicative group.

            (p-1)/q
>>          G         <> I in GF(p^a)   for every prime q dividing (p^a)-1
     
>>     Conversely, if condition is satisfied then G is a generator.


    The finite field GF(p) containing p elements, p prime, has a simple model 
    as modulo arithmetic with modulus p. Is there a simple model for the
    fields GF(p^a) the field with p^a elements with (a > 1) ? In otherwords
    how would one specify an element G of GF(p^a) so that we could ask if
    it was a generator under multiplication of the non-zero elements?
    Note that modulo arithmetic with modulus p^a fails to be such a
    model since

	    p * p^(a-1) = 0 (mod p^a)

    i.e., p^(a-1) is a zero divisor.

    -Franklin

     re .4
     
     The RSA cryptographic system involves generating two large
     primes p and q such that their product pq is difficult to
     factor [to someone knowing pq but not p or q].  There is a
     discussion in Knuth's books on how to generate such large
     primes [The Art of Computer Programming, Vol. 2].
     
     The method he suggests for a prime p of approximately 120
     digits is:
     
          select a truly random P0 between 10^80 and 10^81
          search for the first prime P1 > P0
          select a truly random P2 between 10^39 and 10^40
          let p be the first prime of the form K * P1 + 1
               for K >= P2
     
          [note that P0, P2, and K are not required to be
          primes in the above]
     
     The prime p is about 120 digits, but by the construction you
     already know the (about 80 digit) prime factor P1 of p-1. 
     It would still be necessary to factor K, but it has only
     about 1/3 as many digits as p does.
     
     I don't know if your application requires special
     properties of p, for example that p-1 be difficult to
     factor.
     
     re .5
     
     There would be an element "x" of the field (of p^a elements,
     a > 1) such that each element of the field could be
     represented by a different polynomial in x with degree < a
     and coefficients the integers modulo p.
     
     For example the field with 125 elements would have the 125
     elements a + bx + cx^2 where a,b,c vary through {0,1,2,3,4}
     and where x represents a root of a third degree polynomial
     with coefficients {0,1,2,3,4} which cannot be factored over
     the polynomials with coefficients {0,1,2,3,4}.  One
     possibility is x^3 + x + 1 = 0.
     
     Dan