3
$\begingroup$

I'm trying to follow this example of ElGamal's encryption scheme (page 2, slides 3 & 4), but don't understand this step (decryption, step 2):

$$(k^x)^{-1} \pmod m$$ Where $$k = 10,\ x = 9,\ m = 13$$

The slide shows that it becomes $$12^{-1} \pmod{13}= 12$$

Where did 12 come from? Also, can you help me see how the above equals 12?

I calculate:$$12^{-1} = \frac{1}{12}$$

  • 1
    You are supposed to work with congruences (and/or residue classes). Because $$12\cdot12=144\equiv1\pmod{13}$$ $12$ is equal to its own inverse in the group of units of the residue class ring $\mathbf{Z}_{13}$. This is even easier to see from the congruence $$12\equiv -1\pmod{13}.$$ Surely $-1$ is equal to its reciprocal.2012-03-20
  • 0
    Okay, I will try to think about what you said. Is the reason why $k^{x}$ became 12 also explained in your comment?2012-03-20
  • 1
    Sorry, I didn't notice that you were also asking about $10^9$. Because $1001$ is divisible by $13$, we have $$10^3=1000\equiv-1\pmod{13}.$$ Therefore we also have $$10^9=(10^3)^3\equiv(-1)^3=-1\equiv 12\pmod{13}.$$ Moral: do not attempt El Gamal (or RSA) unless you are familiar with the arithmetic of congruences and residue classes.2012-03-20
  • 0
    Haha, duly noted. I have no idea why you chose 1001. Is there an another way to solve this without knowing about congruence arithmetic?2012-03-20
  • 0
    You could have just got your answer chatting with people. Anyways, you got a quick answer2012-03-20

2 Answers 2