[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1017.0. "Finding 'generators' in a finite field" by NETMAN::STELL (Doug Stell, DTN226-5245, LKG1-1/C6, Pole A7) Tue Jan 24 1989 19:28

	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

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.  This appears to be true, but only if (p-1) is the
product of primes.  If the factorization of (p-1) contains powers of
primes, then additional candidates fail to be generators, but why?  What
is the test for these? 

Another text states that "the odds of getting a generator by random guess 
depend heavily on the factorization of p-1" and that those odds can 
approach zero for certain primes.  This text also fails to hint at the 
test to test used to weed out the additional candidates that fail to be 
generators.

Your help would be appreciated.
				doug stell

T.RTitleUserPersonal
Name
DateLines
1017.1AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoTue Jan 24 1989 21:5019
     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
1017.2racking memoryHERON::BUCHANANAndrew @vbo/dtn8285805/ARES,HERONTue Jan 24 1989 21:5766
1017.3detailsHERON::BUCHANANAndrew @vbo/dtn8285805/ARES,HERONTue Jan 24 1989 22:0815
>     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
1017.4thanksNETMAN::STELLDoug Stell, DTN226-5245, LKG1-1/C6, Pole A7Wed Jan 25 1989 19:4618
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
1017.5Model for GF(p^a), a>1 ??HPSCAD::HERMANWed Jan 25 1989 20:0824
>     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
1017.6AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoWed Jan 25 1989 22:1544
     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