• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Large Calculations in C

dougreed

Member
Joined
Mar 17, 2006
Messages
287
Location
Austin, TX
Hi all,

I'm writing a little RSA cipher program in C for the heck of it, and came across the issue of calculating the modulus of large numbers (e.g. 17^263 % 14351). "long long int" variables are not big enough for my purposes, and the modulo operator expects two ints, so even if "long long int" were big enough I'd have to cast the result to type int anyway.

Does anyone have any ideas as to how I can calculate these large numbers? I can do it by hand, and I suppose I can turn the algorithm I know on paper into some C code, but that really seems like a lot of trouble.

-Doug
 

dougreed

Member
Joined
Mar 17, 2006
Messages
287
Location
Austin, TX
I'm not exactly sure what you mean. You mean divide 17^263 in half? or just 263?

One way to do it is like this:

17^263 % 14351 = 17^(256+4+2+1) % 14351 =
(17^1 % 14351)(17^2 % 14351)(17^4 % 14351)(17^256 % 14351) % 14351

Then we know that

17^1 % 14351 = 17
17^2 % 14351 = 289
17^4 % 14351 = 11766
17^8 % 14351 = 11766^2 % 14351 = 9010
17^16 % 14351 = 9010^2 % 14351 = 10844
...
17^256 % 14351 = [...]

That's about the only way I can figure to calculate these numbers. Then again, that algorithm sure does seem like it would be a pain to code.

-Doug
 
Top