Re: Generator of a group

From: Marcel Martin (mm_at_nowhere.net)
Date: 01/05/05 

Date: Wed, 05 Jan 2005 15:38:33 +0100

Mok-Kong Shen a écrit :
>
> Marcel Martin wrote:
> > Tobias Ruske a écrit :
> >
>
> >>I've been looking for an algorithm, to find a generator g of the group
> >>of quadratic residues modulo p (p is a prime). Can anyone help me?
> >
> > Assuming p is odd, suppose x is a primitive root modulo p and
> > consider the p-1 terms of the sequence:
> >
> > 1, x, x^2, x^3, x^4, ..., x^(p-2)
> >
> > Since this sequence is a permutation of 1,2,3,...,p-1, it contains
> > all the quadratic residues modulo p and these ones are given by the
> > sub-sequence:
> >
> > 1, x^2, x^4, ..., x^(p-3)
> >
> > If a power of x can generate this sub-sequence then it is the
> > generator you want.
> > Yes, now, your problem is "how to find a primitive root modulo p and
> > to square it?" :-)
>
> Wouldn't the way as indicated in HAC 4.80 be better than
> via finding a primitive root? Thanks.

As Phil answered, HAC 4.80 _is_ "how to find a primitive root".

What I wanted was to show to the OP the link between a generator
of the multiplicative group of Z/p (a primitive root) and a
generator of the quadratic residue sub-group. But I wanted to
do that without using formulas (beginners can make use of formulas
but does it make that they really understand what they are doing?) 

-- 
mm
http://www.ellipsa.net/

Relevant Pages

  • Re: related to group theory
    ... but 3 is not a generator surely. ... When n is either an odd prime power, twice an odd prime power, 2, or ... So, if you already know a primitive root, then it is very easy to find ... 2 is a primitive root modulo 10. ...
    (sci.math)
  • Re: eulers phi-function and divisibility by primes
    ... Gottfried Helms wrote: ... For any odd prime p, there are counterexamples (it will be true for ... pick a primitive root g modulo p^2; ... known that such a primitive root will be a primitive root modulo p^n ...
    (sci.math)
  • Re: questions on Diffie-Hellman prime selection on small generator cases
    ... > Diffie-Hellman. ... Ideally the generator should be a generator of the ... prime-order subgroup, not a primitive root. ... with a safe prime. ...
    (sci.crypt)
  • A PRNG based on the DLP
    ... Here is another approach for a secure pseudo-random number generator, ... Choose a random prime number P with B bits in size, and a primitive root ... Experimenting with it has shown that the cycle length for fwill not ...
    (sci.crypt)
  • Re: eulers phi-function and divisibility by primes
    ... p^divides a^} - 1. ... pick a primitive root g modulo p^2; ... known that such a primitive root will be a primitive root modulo p^n ... Thus, plugging g for a, you can see that unless ...
    (sci.math)