# Confusion regarding computing Multiplicative Inverse Modulo P?

May be a silly doubt, please rectify my confusion regarding below problem:

For concreteness assume $g=2, p=11, a=6$ and $x=9$

$$A = g^a \bmod p = 2^6 \bmod 11 = 9$$

$$X = g^x \bmod p = 2^9 \bmod 11 = 6$$

$$C = A^x \bmod p = 9^9 \bmod 11 = 5$$

To find $X$ (i.e. $g^x$) using $C$ and $a$ only is:
$X' = C^{a^{-1}} \bmod p = 5^{6^{-1}} \bmod 11 = 5^2 \bmod 11 = 3$

The answer should be $X = X'$ but it is $X \neq X'$
Why this problem, where is my mistake?

• $6 \times 2 = 2 \mod \phi(11)$. – Henrick Hellström Sep 2 '15 at 11:56

Indeed, theoretically $$X'\equiv C^{a^{-1}}\equiv A^{x*a^{-1}}\equiv g^{x}=X\pmod p$$
should hold, given $gcd(a,p-1)=1$.
1. You calculated $a^{-1}$ using the wrong modulus. As it is in the exponent you need to calculate $a^{-1}\bmod q$ with $q$ being the group's order instead of $a^{-1}\bmod p$. In your example $q=p-1=10$.
2. The value you have for $a$ makes it impossible to invert. For $a^{-1}\bmod q$ to exist $gcd(a,q)=1$ must hold, but $gcd(6,10)=2\neq1$ so there's no $a^{-1}\bmod q$ for your specific choices of $a$ and $q$.
• @user26489, "yes" to your first post. Concerning your second comment: If Inverses are required one usually constructs $p=rq+1$ with $p,q\in \mathbb P$ with $r=2$ being a somewhat common choice (for ElGamal / DH). Then you choose a generator that generates the subgroup of order $q$. For example consider $q=5$and $p=11$, as generator $g$ you'd then choose $g^r\bmod q$ meaning $g=4$. As $4$ has indeed order $5$ means you can use this group. – SEJPM Sep 2 '15 at 17:12