Large Number Storage

Question

I am trying to implement the RSA Key Generation algorithm for a school project. I am having trouble with the encryption stage of the algorithm. It requires me to raise a user inputted integers to the power of a random number (random number has a criteria) and these random numbers are usually 2 or 3 digits long; eg. 23^239 = d. In most situations, the 'd' value is 100s of digits long and I cannot find anything to store it as. I have tried long long but the return value is always negative.

How can I generate and store very large numbers?

Take a look at this question: http://stackoverflow.com/questions/124332/c-handling-very-large-integers — David says Reinstate Monica, May 23 '14 at 13:18
[boost::multiprecision](http://www.boost.org/doc/libs/1_55_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html) is a solution for big numbers. — Innkeeper, May 23 '14 at 13:20
if the answer helps you, accept it. It'll help both you and the answerer have more reputations — phuclv, May 30 '14 at 04:20

score 4 · Answer 1 · answered May 23 '14 at 14:10

All exponentiation in RSA is modular exponentiation. That is, you'll never just compute 23^239... instead, you'll compute something like 23^239 mod 11. You could calculate the exponentiation, and then calculate the modulus.... but as you've seen, that requires the ability to represent a pretty big number. Instead, one does the two operations at the same time; this is much more efficient, and does not require much storage space.

See https://en.wikipedia.org/wiki/Modular_exponentiation for more details, and algorithms.

(Note that, ordinarily, you would still need a bigint library for RSA, because you'd be working with numbers hundreds of digits long, not 2 or 3 digits long. The assignment here seems to have been designed to keep you from having to do that, though.)

Large Number Storage

1 Answers1