Due Wednesday, 21 September, 2016 at 11:30 PM

Report problems to ablumer via email

A lot of cryptographic algorithms need to calculate extremely high powers of integers. To keep these values in a reasonable range, they are reduced modulo another integer. In this assignment, you will explore an efficient way to calculate these powers and get practice with the GMP library. For documentation on GMP, see the reference on the "Links" page.

Here is a short C++ program to calculate an integer value raised to a positive
integer exponent modulo another integer:

/* Simple program to calculate powers */ #include <iostream> #include <gmpxx.h> using namespace std; int main (void) { mpz_class base, result, exponent, modulus; cout << "Enter base: "; cin >> base; cout << "Enter exponent: "; cin >> exponent; cout << "Enter modulus: "; cin >> modulus; result = base % modulus; for (int i=1; i < exponent; i++) { result = (base * result) % modulus; } cout << base << " to the "; cout << exponent << " modulo " << modulus << is\n"; cout << result << "\n"; return 0; }

Create a copy of this program in a directory of your choice. The easiest way
to obtain a copy is to copy it from my home directory using the command

`cp ~ablumer/modcalc.cpp .`

while in the directory of your choice. (Note the spaces before and after "~ablumer/modcalc.cpp")

Compile it using the command

`g++ modcalc.cpp -lgmpxx -lgmp -o modcalc`

which will create an executable file named "modcalc" in your current
directory that can be executed using the command

`./modcalc`

This is far to inefficient to use with the size of exponents typically used for cryptography. Modify this program by writing a subroutine to do the exponentiation using the following idea:

- If the exponent is even, then then x
^{n}mod m can be calculated as x^{(n/2)}* x^{(n/2)}mod m - If the exponent is odd, then then x
^{n}mod m can be calculated as x^{((n-1)/2)}* x^{((n-1)/2)}* x mod m

Calculate some small powers of 2 and 3 modulo various integers to verify that
it works properly. Document your code so that it's easily understandable by the grader.
Please put your first name, last name, and CS login name on the first line of your comments.

Submit your file using this command (substitute a different name if your file
isn't called "modcalc":

`provide comp165 a1 modcalc.cpp`