Archived

This topic is now archived and is closed to further replies.

Shadow Mint

Large numbers: Mod, Pow

Recommended Posts

I''m playing with RSA, and I''m trying to find some algorithms to implement Mod and Pow for really really big numbers. Any suggestions? I can''t think of any decent keywords for google; I''m just getting rubbish about how to RSA, nothing on how to handle big numbers. ciao!

Share this post


Link to post
Share on other sites
Here's the trick: don't implement a big version of pow, and a big version of mod. Instead, implement a big version of pow-mod.

First: remember that
(a^b) mod c  
is the same as
(((a^(b-1)) mod c) * a) mod c  
. so you don't need to store a huge power, then calculate the mod. Instead, you can iteratively calculate it, each time multiplying the product so far with a, then modding it again. The product never goes above c, and the ultimate result is the same as if you multiplied it all out.

But we can do better. keep in mind that
(((a^b) mod c)^2) mod c  
is the same as
(a^2b) mod c 
. So you can calculate all the powers-of-two you need, and then selectively multiply some together. Bingo! efficient modular exponentiation (which, BTW, is the phrase you should Google for for more info.)


How appropriate. You fight like a cow.

[edited by - sneftel on April 28, 2003 4:41:34 AM]

Share this post


Link to post
Share on other sites
Sneftel hit the problem right on the head. Power exponentiation is the method you should use. Once you have gotten this part implemented, you should look at the BigInt class over on Codeguru.com. Here is the link:

You can use this class to implement large integers, although, I would recommend writing your own as an exercise if you have the time. I learned a lot about multiplication shortcuts and stuff when I was writing my own class a few months ago.

If you are really interested in learning more about modular arithmitic, pick up a number theory book. It forms the basis of RSA and it helps if you want to develop your own methods of encryption.

Brendan

Share this post


Link to post
Share on other sites
lol. I did, but the damn book has -ERRORS- in the examples and even some of the algorithms it gives. =P!

And this is "Cyrptography and network security, 2nd ed", Stallings. Avoid it and go for the 3rd ed in my oppinion...

Share this post


Link to post
Share on other sites