I'm trying to write my own RSA implementation using the textbook approach — which I know is not optimal — of picking primes $p$ and $q$, then computing Euler's totient $phi$, then randomly picking an 'e' which is relatively prime to $phi$, and then computing a $d$ such that ($d*e$) mod $phi$ = 1.

For that last step, I'm using the algorithm provided at http://www.pagedon.com/extended-euclidean-algorithm-in-c/my_programming/

This algorithm often yields a negative $d$, which sure enough does satisfy $d*e$ mod $phi$ = 1. But obviously I can't use a negative $d$ as the exponent during decryption.

Is there some straightforward way I can amend this algorithm, Or is it rather my understanding that needs amending?

  • $\begingroup$ You can use negative d for decryption: $c^{-d} = (c^{-1})^d$, $x$ to minus $d$ is the inverse of $x$ to $d$. Not that anyone would do it that way... $\endgroup$
    – K.G.
    Commented Oct 6, 2013 at 20:10

2 Answers 2


In modular arithmetic all of $a + k \cdot m$ with modulus $m$ and integral $k$ are equivalent. You need to solve this equation modulo $\phi$. So $-x$ is equivalent to $-x + k\cdot \phi$ with a sufficiently large $k$ to make it positive.

In code you can use something like:

d = d % phi;
if(d < 0)
    d += phi;

In addition to what CodesInChaos stated (which does apply): the code you linked to does not support integers bigger than the maximum for the C int type, typically $2^{31}-1$. This is not enough in an RSA context, and may cause problems similar to what you have. You can

  • switch to a language with built-in support for big integers, like Python, Java..
  • use a C or C++ bigint package, like GMP;
  • roll your own bigint package.

Also, beware of the code you linked to: it is a bit on the complicated side, and does not detect when there is no modular inverse for the given parameters..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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