Re: FLTMA: A little group theory


The Dougster wrote:

In such group of numbers coprime to modulus m, there will be a
generator a, such that the powers of a, { a^n | n is in Z } are
precisely the elemrnts of the group. How many generators will there be?
Well, there are phi(m) elements in the group. There are phi^2(m) or
phi(phi(m)) generators coprime to phi(m).

We sorted through this earlier. The (multiplicative) group
of residues coprime to modulus m is not generally cyclic
and doesn't have a generator except in special cases.
[See earlier msg for a list of these and references.]

Perhaps you have in mind a notion of an (abelian) group
that is generated by a minimal subset of more than one
element. For example, we noted the multiplicative group:

Z/16Z* is isomorphic to Z/2Z X Z/4Z

Here we may speak of residues 3 and 15 mod 16 as
(jointly) generating Z/16Z*, but there is no single
generator because no element has order > 4.

regards, chip

.

Relevant Pages

  • Re: algebraic question
    ... >that g is a generator of the multiplicative group of the ring Z_p. ... Somehow I misinterpreted G to be the multiplicative group of the ring ...
    (sci.math)
  • Re: general question how to choose parameters
    ... Basically, the multiplicative group mod ... > get stuck in one of the small subgroups, ... like in the ElGamal-case g as a generator of Z_p^*? ... If an attack is possible in 2.) ...
    (sci.crypt)
  • Re: Irreducible
    ... I think Mr. Montgomery refers about degree of alpha as ... No, your proof is the same as the flawed proof I posted yesterday, and ... generator of the multiplicative group of k. ...
    (sci.math)
  • Re: squareroots in gf(2^m)-
    ... Therefore each element of GF, not only zero, has a =unique= square root. ... Once one has a generator of the multiplicative group, all relevant calculations are done by halving and doubling exponents modulo ...
    (sci.math)
  • Re: public key crypto
    ... Kristian Gjøsteen wrote: ... >>I'm pretty sure I've seen a proof that a generator exists for all Zp, ... the multiplicative group is cyclic. ... for the primitive roots, that are shown to exist by the ...
    (sci.crypt)
Loading