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?