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
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)
