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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Recently I was looking at the RSA encryption scheme and decided to do some examples but this seemingly simple one is bugging me a lot.

I chose $p=13$, $q=17$. Let $e=131$, be the encryption key. So, $\phi=(p-1)(q-1)=12 \times 16 = 192$

I need to compute $d$, the decryption key. So I used extended Euclid's algorithm to solve the equation $de-k\phi=1$. (Since $d$ needs to obey the condition $de \equiv 1 \pmod \phi$.)

As a result I got this strange looking solution $-85 \times 131 + 58 \times 192 = 1$. That is, it says, $-de+k\phi=1$ (to me it looks strange because it says $d$ is negative and I haven't worked with negative values of encryption or decryption keys before. If $d$ can be negative, as it seems to be in this case, how do I compute $M^d$, for example if I want to compute the digital signature of the message $M$?. Moreover, the value of $d$ that I obtained ($-85$), doesn't seem to obey the condition $de\equiv 1 \pmod \phi$. You plug in the values for $d$,$~e$ and $\phi$, and you get a different result. I am totally lost and I don't understand what's going on here. Please correct me if my understanding is wrong and point me in the right direction.

If I assume $d=85$ and compute the signature for say, $M=87$, it results in some value, which when verified with $e=131$, doesn't give $85$. I appreciate any help. Thanks.

share|cite|improve this question
$d$ is only defined up to congruence mod $\phi$. So $d=-85=192-85=107$. – Chris Eagle Oct 24 '11 at 9:57
I plugged in $d,e$ and $\phi$ and I didn't get a different result. But $-85=107\mod 192$ so that's the $d$ you should be using. – anon Oct 24 '11 at 9:59
up vote 3 down vote accepted

Once you know $$-85\times 131+58\times 192 = 1$$ you can add $192\times 131-131\times 192$ from the left-hand side to get $$(192-85)\times 131+(58-131)\times 192=1$$ So your sought inverse modulo $192$ is $192-85=107$.

share|cite|improve this answer

Your Answer


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.