Re: generators be bound

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 10/24/03 

Date: 24 Oct 2003 11:56:58 -0700

[Missing articles again...]

In article <iX7mb.273537$ko%.94523@news04.bloor.is.net.cable.rogers.com>,
Tom St Denis <tomstdenis@iahu.ca> wrote:
>
>"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message
>news:3F988551.610D9516@t-online.de...
>>
>>
>> Tom St Denis wrote:
>> >
>> [snip]
>> > So what should I have said to mean a generator of a sub-group of a
>given
>> > order?

In the description of the Digital Signature
Standard algorithm, the terminology is "generator
of the order-q subgroup". That's exactly what's
meant.

>That's just my point. According to the folk here that's not a generator.
>Unless it generates the entire group it's just a ??? [blank]

If it doesn't generate the whole group, it's not a
generator of the whole group. It does, by
definition, generate some subgroup, but unless you
are referring to the subgroup explicitly or
implicitly, you can't just call it a generator.

>What really happens is all generators are in fact primitive [to some
>sub-group]. Take Z/7Z for instance. There will be sub-groups of order 2, 3
>and 6. Note that Z/7Z actually has 7 elements so the group of order 6 must
>be a sub-group of it as well. There will be an element [g=3] which
>generates an order 6 group but there are also elements which generate
>smaller sub-groups [e.g. g=2 genrates a group of order 3].

No, that's incorrect terminology too. Sorry. Z/7Z
is a *field*. It has two group operators, + and *
(call them). w.r.t. +, there's only one subgroup,
which is the identity subgroup. All non-zero
elements generate the entire group.

The 6-element group with * as its operator is
called the "multiplicative group". It's not a
subgroup, unless you consider it in light of being
a subset of the *field*. Anyway, the rest of what
you say is correct.

>The point is w.r.t the 3 element sub group {2, 4, 1} of Z/7Z g=2 is
>primitive since it generates the entire group. w.r.t. Z/7Z multiplicative
>sub-group {3,2,6,4,5,1} g=2 is not primitive.

Correct.

>Not to abuse notation though. I agree that without further details
>"generator" should therefore be w.r.t. the multiplicative group of maximal
>order [as others stated]. My point though is that it isn't invalid to say
>"g=4 is a generator of prime order modulo a safe prime". It really does
>generate such a sub-group.

Sure. Your facts and understanding are not in
dispute, only a nitpick of terminology.

Greg. 

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

Relevant Pages

  • Re: generators be bound
    ... >> definition a generator of that subgroup. ... According to the folk here that's not a generator. ... Generator of a proper subgroup. ... "the multiplicative group of maximal order" is ...
    (sci.crypt)
  • Re: normalizer of Q8 in SL(2,q)
    ... Edwin Clark wrote: ... This commutes with the first generator, ... automorphism group by the inner automorphisms is isomorphic to S_3. ... Hence N/Q_8 is isomorphic to a subgroup of S_3. ...
    (sci.math)
  • Re: Parameters for Diffie-Hellman-Merkle
    ... Richard Heathfield wrote: ... >Paul Crowley wrote: ... then it's a generator of the order Q subgroup. ...
    (sci.crypt)
  • Re: generators be bound
    ... > Tom St Denis wrote: ... if you have a subgroup of a cyclic ... According to the folk here that's not a generator. ... be a sub-group of it as well. ...
    (sci.crypt)
  • Re: Multiplicative Homomorphic Mapping
    ... the pairing eis a generator of a subgroup in F_p^l ... This is a very special instance and what I want to find is other more ...
    (sci.math)