Re: RSA decryption exponent d (c++)

Timo Johansson <johansson@despammed.com> wrote:
>TJakobsen wrote:
>>d is calculated like this:
>>
>> d = e^-1 (mod phi(n))
>
>d = e^{-1} = e^{phi(n)-1} (mod phi(n))
>
>since phi(n) = 0 (mod phi(n))

You are on the right track, but missing a phi:

        e^{-1} = e^{phi(phi(n)) - 1} (mod phi(n))

by Euler's theorem.

>The result is a quite huge number, but you can use modulo reduction after
>every multiplication:

Observer that your code is no faster than searching for an inverse.
If you had used square and multiply to exponentiate, this would
have been faster.

-- 
Kristian Gjøsteen