Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Jyrki Lahtonen Mar 20 '12 at 17:44
    
Okay, I will try to think about what you said. Is the reason why $k^{x}$ became 12 also explained in your comment? –  Louis Mar 20 '12 at 17:59
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. –  Jyrki Lahtonen Mar 20 '12 at 18:03
    
Haha, duly noted. I have no idea why you chose 1001. Is there an another way to solve this without knowing about congruence arithmetic? –  Louis Mar 20 '12 at 18:08
    
You could have just got your answer chatting with people. Anyways, you got a quick answer –  Kirthi Raman Mar 20 '12 at 18:13
add comment

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
    
Whoever downvotes should be nice and give constructive criticism! –  user2468 Mar 20 '12 at 20:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.