Re: algebraic question

On Wed, 20 Jul 2005 11:16:42 -0700, quasi <quasi@xxxxxxxx> wrote:

>On Wed, 20 Jul 2005 16:41:39 +0200, Johanna Bernstein
><johanna_bernstein_nospam@xxxxxxxxx> wrote:
>
>>Hello group,
>>
>>I have an hopefully simple question:
>>Let p,q be large primes with p=2q+1. Let g be a generator of a group G
>>of order p. Let x \in Z_p^*. Now I compute:
>>A = g^x.
>>Is there a second value x' != x with A =g^{x'}?
>>
>>Thanks in advance,
>>Johanna
>
>Hints:
>
>Suppose g^x = g^(x').
>
>Simplify that equation to get g^(x-x')=1.
>
>But since g generates the group G (what is the order of G?), what can
>be said about the exponent (x-x')?
>
>Note: For this problem, you can ignore the given relationship p=2q+1.
>It plays no role in the proof. All you need is that p is prime and
>that g is a generator of the multiplicative group of the ring Z_p.
>
>quasi

I think I may have read the problem too quickly, sorry.

Somehow I misinterpreted G to be the multiplicative group of the ring
Z_p but of course, then G would have order p-1, not p.

So let me rethink this. G has order p, right? Since p is a prime, the
group G is cyclic, and moreover, every element of G except 1 generates
the group.

Now given any generator g, the argument I previously outlined still
works to show that x=x', and again, there is no need to make any use
of the relationship p=2q+1.

quasi
.

Relevant Pages

  • Re: algebraic question
    ... >Let p,q be large primes with p=2q+1. ... Let g be a generator of a group G ... that g is a generator of the multiplicative group of the ring Z_p. ...
    (sci.math)
  • Re: Please help, Thanks!
    ... To define a ring, you also have to define how elements _add_. ... Alternate hint: Note that R is commutative, ... the fact that the multiplicative group of a finite ...
    (sci.math)
  • Re: algebraic question
    ... be said about the exponent? ... All you need is that p is prime and that g is a generator of the multiplicative group of the ring Z_p. ...
    (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)
Loading