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

1. Feb 20, 2010

### Troff

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 $$y = g^x$$ 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 $$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.

2. Feb 20, 2010

### 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.

3. Feb 20, 2010

### 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.

4. Feb 20, 2010

### 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.

Last edited: Feb 20, 2010