### COMP 165 - Fall 2016 - Homework 1

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 xn mod m can be calculated as x(n/2) * x(n/2) mod m
• If the exponent is odd, then then xn 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