Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Can I calculate the (multiplicative) inverse of any element in a cyclic group?

  1. Feb 20, 2010 #1
    1. The problem statement, all variables and given/known data
    The original problem has to do with telling messages encrypted with a version of the ElGamal public key crypto system apart. It relies on exponentiation in an arbitrary cyclic group G of prime order p with generator g. The public key is [tex]y = g^x[/tex] where x is the private key.

    2. Relevant equations



    3. The attempt at a solution
    Well - I don't actually want help finding a solution to the original problem, but the solution that I do have relies on the ability to calculate [tex]y^{-1}[/tex]. As far as I can tell [tex]\forall x \in G: x^{p} = 1[/tex], which would seem to imply that [tex]\forall x \in G: x^{p-1} = x^{-1}[/tex]. Either this is wrong in which case I'd like to understand what I'm missing or I am doing something wrong somewhere else, which I'd then correct or fail myself.
     
  2. jcsd
  3. Feb 20, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Almost right. Fermat's theorem tells you x^p mod p is x. Not 1. The group actually has p-1 elements in it.
     
  4. Feb 20, 2010 #3
    Yes, but the order of the group is what is given and I can't assume that we're in [tex]\mathbb{Z}^*_p[/tex] so modular arithmetic and Fermat's theorem seem to be an isomorphism away (at least). But apart from the exact value of the exponent you seem to agree that it's possible to efficiently calculate the inverse.
     
  5. Feb 20, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right. I was thinking of multiplicative Z_p. In that case I agree. x^(p-1) is the inverse of x where p is the order of the group. In fact, I don't think you even need to assume G is cyclic or that p is prime for that.
     
    Last edited: Feb 20, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook