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

[Troff]

Homework Statement

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 y = g^x where x is the private key.

Homework Equations

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 y^{-1}. As far as I can tell \forall x \in G: x^{p} = 1, which would seem to imply that \forall x \in G: x^{p-1} = x^{-1}. 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.

 

[Dick]

Almost right. Fermat's theorem tells you x^p mod p is x. Not 1. The group actually has p-1 elements in it.

 

[Troff]

Yes, but the order of the group is what is given and I can't assume that we're in \mathbb{Z}^*_p 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.

 

[Dick]

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.