Large Calculations in C

[dougreed]

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

 

[pjk]

Make divide the int in two and have two separate outputs.

 

[dougreed]

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

 

[pjk]

Divide the answer that is outputted in half. Or maybe have the decimal moved on the output.