1

So of course I know there are simple solutions to this such as using the GMP library or numerous other arbitrary-precision libraries. This is for class work so I am not allowed to take any of these routes. After we build up all our operations we are leading up to be able to do a RSA encryption scheme.

I am using vectors to store n-bit numbers represented in binary. I have conversions to decimal later but I must operate on the binary and only convert for display.

I have successfully implemented addition, subtraction, and multiplication. I am stuck on division and modular operations... specifically modular exponentiation. I understand the algorithms at least at a basic level but cant seem to translate it into code that will work on arbitrary length numbers. I cant seem to find any examples of this type of work done in c++ without external libraries.

Some specific questions:

is there a better way to do modulus on a n-bit number besides just calling the division function I am writing and using the remainder returned?

I really would love to see some good c++ examples as I cant follow the GMP source code well at all.

Any good resources to study or some help would be greatly appreciated. Thanks

Wildcat313
  • 23
  • 3

1 Answers1

1

You can fake modulus operations with division. Your modulus operation is equivalent to:

v = n - (n / m) * m

where n is the divisor, m is the modulus, and v is the output value (all arbitrary precision numbers)

If you're stuck on division you can just implement it like you would perform long division by hand. (You should have learned how to do this in middle school via multiplication and subtraction. It's easy enough to translate the process to base 2. Do a few on paper if you're stuck. If you want a more efficient algorithm, you can probably find one by searching on google for something like "arbitrary precision division algorithm")

Once you have modulus, you can compute modular exponentiation with repeated squaring. Observe as we compute some large integer X to the power of 67, mod N:

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

Mathematically, you can see why this makes sense. This algorithm is the generally chosen algorithm for computing modular exponentiations, and operates in time and space logarithmic to the size of the exponent and logarithmic to the size of the base (i.e. it's fast, even for huge numbers)

P.S. Make sure you tell your professor he's silly for not letting you use external libraries. One of the most important things programmers can learn is when to be lazy (i.e. when to find and use a library to do something rather than homebrewing your own solution)

Wug
  • 12,956
  • 4
  • 34
  • 54
  • 1
    Man that stinks. This was a great answer until the philosophical waxing. There's a differences between "someone else did it so you don't *need* to" and "someone else did it so you don't need to *learn* *how* *to*. Newton studied Da'Vinci. He dind't just take his lifetime of notes and say "f'it. I don't need to care how this works, that smart guy did it already." – WhozCraig Sep 26 '12 at 20:53
  • Knowing when to be lazy is an essential skill that improves your real world output. When you have a job, you can google for help, you can use libraries; all of the artificial academic restrictions are gone. Yes, its great to know how something works, but if all you are really interested in big integer logic, take a peek at an existing library; to write your own naive, incomplete, buggy implementation would be a waste of your time. – Wug Sep 28 '12 at 02:05
  • Agreed. No reason to reinvent a wheel that someone else did already. My point was that when that wheel breaks and you have absolutely no knowledge how it should work, you're hosed. Its not the product; its the know-how. Utilizing someone else's hard work without the foggiest clue what makes it work puts your future literally in the hands of an unknown. *You* can control it by becoming familiar, by studying, by *learning*. That was my whole point. And I meant what I said, I really did like the answer. Very well presented. – WhozCraig Sep 28 '12 at 02:44
  • Thank you. I don't know how far along in your education you are, but the further I get through mine, the more I realize things like proper design and intentional laziness are important, and the larger your project gets, the more important it is to save time those ways. For the record, I've tried to write a biginteger library in C++, and it's not easy. I wasn't doing it for a specific reason except to see if I could, and I gave up on it after a while. – Wug Sep 28 '12 at 03:30