Re: Generator of a group

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 01/07/05


Date: 6 Jan 2005 21:44:12 -0800

In article <crkgol$gj0$00$1@news.t-online.com>,
Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>Greg Rose wrote:
>> I'm not aware of any way to do it without knowing
>> the factors of p-1, and I have a strong feeling
>> that there can't be one, but I'd be happy to be
>> corrected on this.

>I don't yet see why the case (p-1)/2 is prime could be
>more advantageously treated as compared to the case where
>the factorization of (p-1)/2 is unknown (and one resorts

Gee, Mok-Kong, you've outdone yourself here.

If (p-1)/2 is prime, you *know* its factorization.
Any generator of the multiplicative group must either be:
1. the identity (generates the order 1 subgroup)
2. -1 (generates the order 2 subgroup)
3. a generator of the group of quadratic residues
4. a generator of the whole group.

The order of a subgroup must divide the order of
the group. The order of the multiplicative group
mod p is p-1. P is prime, so it's odd, so p-1 is
even, so 2 divides p-1. If (p-1)/2 is prime, there
just ain't any other possibilities.

I know that you usually argue for argument's sake,
which is why I won't usually argue against you,
but this is simply fatuous.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au


Relevant Pages

  • Re: Generator of a group
    ... >I search the generator of the group of quadratic residues for a prime p ... >value and it's hard to find the factorization for such a big ... the factors of p-1, and I have a strong feeling ... Greg Rose ...
    (sci.crypt)
  • Re: Poker Tests in restricted envionments
    ... >> generator that collects bits of data from a transistor noise source, ... done with a binomial test. ... So, the binomial formula ... Greg Rose ...
    (sci.crypt)
  • Re: Java encryption implementation
    ... >so you cannot derive the exact value of the generator, ... as the random number generator for DSS, ... (Crypto '97, my first Crypto! ... Greg Rose ...
    (sci.crypt)
  • Re: Generator of a group
    ... >of quadratic residues modulo p. ... If it does, it is a generator. ... start again with another random element. ... Greg Rose ...
    (sci.crypt)