How does one deal with a negative "d" in RSA? 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?
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 &lt; 0)
    d += phi;