Re: RSA question

tomstdenis_at_gmail.com
Date: 08/10/05


Date: 10 Aug 2005 10:57:58 -0700


John Smith wrote:
> In the RSA algorithm the private key d is choosen such that
>
> d*e = 1(mod(p-1)*(q-1))
>
> How can d be calculated directly, that is, without resorting to a brute
> force search? An example with small numbers would be helpful.

Look up the "extended euclidean algorithm" which is covered in any
number theory text as well as various computer science texts such as
"The Art of Computer Programming". Failing that you can google or look
on mathworld and failing that ask the resident expert, Mr. Regis.

Tom