I've just completed a program which does arithmetic on arbitrarily large integers, and I'd now like to implement RSA encryption with it. Unfortunately, it seems that I am doing things very inefficiently. I have a binary powering routine, and am trying to calculate a number on the order of:
50^(2^512) (mod 2^1024)
The program grinds to a halt almost immediately, because the powers of 50 soon become incredibly large.
I'm not aware of any techniques for RSA encryption except binary powering, but I'm sure there must be cleverer ways to do it. Does anyone have any advice?