Re: RSA decryption exponent d (c++)

Hello,

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))

> I have used the following numbers:
>
> p = 37
> q = 89
> n = p*q = 37*89 = 3293
> phi(n) = (p-1)(q-1) =3168
> e = 25

So, maybe it's more simple for you to compute

e^{phi(n)-1} = 25^3167

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

unsigned long int d,e;
int i;

e=25;
d=25;
for(i=0;i<3168-1;i++){
  d *= e;
  d %= 3168;
}

although i'd prefer using the extended euclidean alg...!
Remark, this is a quick shot and not tested, so I'm almost shure there are a
few mistakes, but I guess you got the idea of what I mean...

regards, Timo
Received on Mon May 1 01:54:16 2006