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

2

Mod $13\!:\ 10\equiv -3\:$ so $\rm\: 10^9 \equiv ((-3)^3)^3\equiv (-27)^3\equiv (-1)^3\equiv -1,\:$ and $\rm\:(-1)^{-1}\equiv -1\equiv 12$

As above, generally modular arithmetic is easier using the least residue reps $\:0,\pm1,\pm2,\ldots, \pm6\:$ versus $\:0,1,2,\ldots 12\:$ modulo $13$.

1

Over the rationals, $\mathbb{Q},$ we have $$ 12^{-1} = \frac{1}{12}$$ but over the integers modulo $13,$ $\mathbb{Z}_{13},$ we have $$ 12^{-1} \equiv x \pmod{13}$$ were $x$ is the multiplicative inverse of $12$ modulo $13.$ To find $x,$ follow this argument. Since $$12^{-1} \equiv x \pmod{13},$$ we have $$12a \equiv 1 \pmod{13}.$$ Recall $1 \pmod{13} = 1 + 13k$ for some integer $k.$ So $ 12x = 1 + 13k .$ Rearrange, $$ 12x - 13k = 1.$$ This is similar to what the extended Euclidean algorithm gives us: $$ 12x + 13k = \gcd(12, 13).$$ So compute the extended Euclidean algorithm on $12, 13$ you will get $12$ as the inverse (here is one nice online calculator and another one; both perform extended GCD).


Another method is to construct the multiplication table module $13$ and look for an entry $x$ such that $$ 12x \equiv 1 \pmod{13}$$

  • 0
    Whoever downvotes should be nice and give *constructive* criticism!2012-03-20