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}$

  • 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