Re: Generators of cyclic group

From: Marcel Martin (mm_at_ellipsa.no.spam.net)
Date: 10/29/03

  • Next message: John Hadstate: "Re: manual cryptography" 
    Date: Wed, 29 Oct 2003 17:42:27 +0100

    Mok-Kong Shen a écrit :
    >
    > Michael Amling wrote:
    > >
    > [snip]
    > > The order of an element (defined as the lowest nontrivial number of
    > > copies of the element that multiplied together produce the identity) of
    > > a group has to divide the order of the group (defined as the number of
    > > elements in the group). This is only a mild hint.
    >
    > I suppose one has to follow the way indicated by
    > Gerry Myerson. If there is another solution of the
    > problem I would appreciate very much to know a bit
    > details.

    I think not. The problem is not "How many generators are there?" but
    "Prove that generators are quadratic non residues (except -1)".

    If x is a QNR, then x^q = -1. By definition, since q = (p-1)/2.
    Now, (x^q)^2 = x^(2q) = (-1)^2 = 1 and x^2 <> 1 (over Z/p, 1 has
    only two square roots: 1 and -1, and they are both excluded).

    In short, if x is a NRQ different from -1, we have (x^2 <> 1) and
    (x^q <> 1) and (x^(2q) = 1), which implies that x is a generator.

    Since the OP already proved that QR cannot be generators, that's
    done.

    mm

  • Next message: John Hadstate: "Re: manual cryptography"