Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I am testing a piece to encrypt and decrypt messages, and I am not 100% on why the algorithm does not seem to work as expected.

My test encryption key $e =27$. My primes $p = 263$ and $q = 911$. And when I run my code to generate a decryption key, $d$, using the algorithm $d\equiv e^{-1} \pmod{ (p-1)(q-1)}$, I get $d=70643$. When I then proceed to decode my cipher, $C$, using the algorithm $C^d \pmod{ (pq)}$, I get something unexpected, and incorrect.

the message m =82020161928606013010912592501081515590315136325211464072101146304100804061004

Anyone have an idea where I may be getting this wrong please? Thanks in advance

share|cite|improve this question
Is it not supposed to be $d \equiv e^{-1} \mod \phi(n)$ where $\phi(n)=(p-1)(q-1)$? – Jalaj Mar 5 '12 at 1:15
oops! I corrected that. Yes, it is and I get d=70643. – Kobojunkie Mar 5 '12 at 1:26
up vote 2 down vote accepted

In Wolfram Alpha I tried $555^{27} \pmod{263*911} \equiv 44315$ then $44315^{70643}\pmod{263*911} \equiv 555$ so it seems to work here.

share|cite|improve this answer
Here is the problem, when I put my Cipher through the same, I don't get the original back. $$106994^70643 (mod 239593)$$ in Wolfram also gives me $$152989$$, which is incorrect – Kobojunkie Mar 5 '12 at 1:43
@Kobojunkie: The message has to be less than the modulus. It is giving you back m mod 239593, so your routines are working fine. Two $\LaTeX$ hints: enclose multicharacter things (like 70643) in braces: 2^33 gives $2^33$ but 2^{33} gives $2^{33}$ and the way to write mod239593 is \pmod {239593}. That way the mod isn't italicized. – Ross Millikan Mar 5 '12 at 3:10
thanks for the tip. – Kobojunkie Mar 5 '12 at 11:08

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.