C++: implementing Modular Exponentiation

Question

I am using this New and improved code I corrected in order to solve this question I have.

I am using modular Exponentiation to use the formula [a^k mod n] to get my answer for an assignment I had to do where I was required to code it in two steps.

First int k must be converted to a binary representation K consisting of a list of 0s and 1s. Second, Modular Exponentiation must be performed using a, n and K[] as arguments..

Earlier My code was incorrect and was able to correct it.

The Problem I now face is that when I google the online calculator for modular Exponentiation of 5^3 % 13, it should == 8

The result that I get from my code is 5. I am trying to understand if there something minor I'm missing from the code or my math is wrong? Thanks

#include <iostream>
#include <vector>
using namespace std;

vector <int> BinaryK(int k);
int ModularExpo(int a, vector <int> & k, int n);

int main()
{
    int a = 0;
    int k = 0;
    int n = 0;

    cout << "a^k % n" << endl;
    cout << "a = ";
    cin >> a;

    cout << "k = ";
    cin >> k;

    cout << "n = ";
    cin >> n;

    vector<int> B = BinaryK(k);
    int result = ModularExpo(a, B, n);
    cout << "a ^ k mod n == " << result << endl;

    return 0;
}

// c == b^e % m

vector<int> BinaryK(int k)
{
    vector<int> K; //hint: make K a vector
    int tmp = k;
    while (tmp > 0)
    {
        K.push_back(tmp % 2); //hint: use pushback
        tmp = tmp / 2;
    }

    return K;
}

int ModularExpo(int a, vector<int> & K, int n)
{
    if (n == 1)
        return 0;

    int b = 1;
    if (K.size() == 0)
        return b;
    int A = a;
    if (K[0] == 1)
        b = a;

    for (int i = 1; i < K.size() - 1; i++)
    {
        A = A * A % n;
        if (K[i] == 1)
            b = A*b % n;
    }
    return (b);
}

Here's [another implementation](http://stackoverflow.com/a/20114154/179910) you can look at if you like. — Jerry Coffin, Mar 08 '17 at 05:26

rcgldr · Answer 1 · 2017-03-08T05:31:27.893

1

Change this one line:

    for (int i = 1; i < K.size(); i++)   // K.size() not K.size()-1

edited Mar 08 '17 at 05:31

answered Mar 08 '17 at 05:18

rcgldr

27,407
3
36
61

it didnt change anything, can you be more specific please? thank you I didnt understand what you mean change that line but with a "-1" cause it didnt work – Mark1247 Mar 09 '17 at 02:22
The exit condition should be `i < K.size();`, with the current code (using K.size()-1), the most significant bit is not being used. – rcgldr Mar 09 '17 at 02:40

C++: implementing Modular Exponentiation

1 Answers1