Examples of functions: x to the y mod m

This exercise continues the development of your knowledge of C++ and the way it handles functions. You will see much more on the use of functions in C++, including

definition by recursion
avoiding recursion when you can
call-by-reference
analysis of algorithms

1. The mathematics

In all cases you will calculate the value of the function,

powmod (x, y, m) = x^{y} mod m

for nonnegative integers $x, y, m$ .

This function is particularly important in cryptography, and it is important to be able to calculate it accurately and quickly.

There are several ways to define this, both mathematically and in C++. Many of these definitions are by recursion.

Definition 1

powmod (x, y, m) = pow (x, y) % m

where % means remainder (in the range $0 \dots m - 1$ ) and

pow (x, 0) = 1

pow (x, y + 1) = pow (x, y) \times x

Remark.

(Note that this means that $pow (0, 0) = powmod (0, 0, m) = 1$ for $m > 1$ . All the definitions will have this as a special case.)

Another idea is to reduce mod $m$ every time a multiplication is performed and not just right at the end:

Definition 2

powmod (x, 0, m) = 1

powmod (x, y + 1, m) = (powmod (x, y, m) \times x) % m

A more subtle third option is also available:

Definition 3

powmod (x, 0, m) = 1

powmod (x, 2 y, m) = ({powmod (x, y, m)}^{2}) % m

powmod (x, 2 y + 1, m) = ({powmod (x, y, m)}^{2} \times x) % m

2. Programming

Here we are going to pretend that we don't have a large library of functions available (such as <cmath>) and consider how we can program the powmod function with only <iostream> for input and output, and we are going to work with int throughout. You can of course use the C++ operators + - * / % and these should be all you need.

Definition 1

Each of the above definitions 1,2,3 yields a C++ function powmod1, powmod2, and powmod3 defined by recursion quite readily. For example, Definition 1 gives a two stage definition

int pow1(int x, int y) {
    if (y<=0) { return 1; }
    return x * pow1(x,y-1);
}

int powmod1(int x, int y, int m) {
    return pow1(x,y) % m;
}

Note in particular how this C++ code follows Definition 1 exactly. All your functions this week should follow the relevant definition exactly in the same way.

Try powmod1 out to check it works.

Important Read this section with the "Testing" section below which contains some suggestions for "main" so that you can test your functions as you go on.

Definition 2

Exercise.

Define a single function int powmod2(int x, int y, int m) in C++ using Definition 2, using recursion. Note: since this is a definition by recursion your function is only allowed to call powmod2 and not any other function. (This is a restriction for this exercise because I want your C++ code to exactly follow the definition, and not a restriction imposed by C++ itself.)

Try the effect of calling powmod2 with a large y, e.g. a million.

Definition 3

Exercise.

Implement int powmod3(int x, int y, int m) using Definition 3 in the same way using recursion. Note: since this is a definition by recursion your function is only allowed to call powmod3 and not any other function.

Note:

You should not call powmod3 more than once in the body of the definition of powmod3. (Why would this be a bad ideas? How can you avoid this by using a new variable?)

Try the effect of calling powmod3 with a really large y, e.g. a billion.

Avoiding recursion

Any of the previous definitions gives a working function, but will not be as efficient as it can be, because the extra overheads with recursion are sometimes quite costly in terms of time and memory (and these overheads become worse when int is replaced by some high precision integer type as required in cryptography). To avoid recursion you need to program a loop. Here is Definition 2 programmed as a loop.

int powmod2loop(int x, int y, int m) {
    int ans = 1 % m;
    for ( int i=0; i<y; i++ ) {
        ans = ( ans * x ) % m ;
    }
    return ans;
}

Exercise.

Implement int powmod3loop(int x, int y, int m) using Definition 3 using the following method.

Using an int variable p and a loop over repeated p = 2*p; instructions, first calculate some power of 2 that is greater than or equal to y.
Initialise a variable for the answer with int ans = 1 % m; .
Now repeat the following for as long as p > 0:
- square ans and reduce mod m
- if y >= p do y = y - p and ans = ( ans * x ) % m ;
- halve p

Try your powmod3loop(int x, int y, int m) out.

Capturing errors

One possible issue with this style of coding is that there might be an error, e.g. if an overflow occurs or if the user gives silly input values such as negative values. It's sometimes very tricky to detect in the program if an overflow occurs, and we will not look at this here, but we can guard against the other kinds of error. Rewrite the function so that it returns an error code: 0 to indicate "no error" or 1 to indicate error. To provide the actual answer it modifies one of its input variables using call-by-reference.

Exercise.

Implement powmod3cbr(x, y, m, ans) using the same method as in the previous exercise, but using call-by-reference. Your function should look like the following (and do exactly what it says in the comment).

/* 
 * returns 1 if either of the inputs x,y is negative or if m <= 0
 * otherwise returns 0 and the correct answer powmod(x,y,n) in ans by using the method of powmod3loop
 */
int powmod3cbr(int x, int y, int m, int& ans) {
    // code here
}

3. Testing

You can build up a single C++ source file with all your functions and main as follows:

#include <iostream>
using namespace std;

// all your functions go here

int main() {

    // code for testing goes here

    return 0; 
}

Your "main" function will not be assessed. It is there for your benefit to test your functions only. If you include other functions they will not be assessed either. (Note: the source file must of course compile correctly whatever you put in it!)

For example, a suitable main to test powmod1 is as follows.

int main() {
    int x = 0;
    int y = 0;
    int m = 0;
    cout << "Enter x y and m separated by spaces: ";
    cin >> x;
    cin >> y;
    cin >> m;
    cout << "x==" << x << " ";
    cout << "y==" << y << " ";
    cout << "m==" << m << " ";
    int p = powmod1(x,y,m);
    cout << "powmod(x,y,m)==" << p << endl;

    return 0;
}

You can test powmod2 powmod3 powmod2loop powmod3loop in the same way. You could also test some or all these functions simultaneously in the same "main" to see if they give the same answer.

If you want to save an "old" main() you can keep it but rename it. Then it will still compile but won't run unless it's called. ("main" is after all just an ordinary function.)

The function powmod3cbr(int x, int y, int m) is tested in a slightly different way. I suggest,

int main() {
    int x = 0;
    int y = 0;
    int m = 0;
    cout << "Enter x y and m separated by spaces: ";
    cin >> x;
    cin >> y;
    cin >> m;
    cout << "x==" << x << " ";
    cout << "y==" << y << " ";
    cout << "m==" << m << " ";
    int p;
    if (powmod3cbr(x,y,m,p) != 0) {
        cout << "an error occurred" << endl;
    } else {
        cout << "powmod(x,y,m)==" << p << endl;
    }

    return 0;
}

Check you understand how this works.

You might find that the testing is more thorough if you write your "main" to produce a table of values, not just one value.

You will have an assessment to do relating to these functions, and an associated quiz. As always check Canvas for details and follow them exactly.