CPP

c++ square and multiply algorithm

#include <iostream>
#include <algorithm>

using std::cout;
using std::endl;
using std::string;
using std::stoi;

/**
 *
 * @param exponent
 * @return string => turns exponent into binary string
 */
string getBinary(int exponent) {

    string expo_Binary;

    while(exponent) {
        expo_Binary += (exponent%2) + '0';
        exponent /= 2;
    }
    reverse(expo_Binary.begin(),expo_Binary.end());

    return expo_Binary;
}

/**
 *
 * @param potenz
 * @param expo_Binary
 * @param modulo
 * @return int => remainder
 */
int getMod(int const base, string const& expo_Binary, int const modulo) {

    int remainder = base;

    for(int i = 1; i<expo_Binary.size(); i++) {
        remainder = (remainder * remainder) % modulo;
        remainder = ( (expo_Binary.at(i)-'0') == 1) ? (base * remainder) % modulo : remainder;
    }

    return remainder;
}

int main() {

    string expo_Binary = getBinary(373); // exponent
    int const remainder = getMod(23, expo_Binary, 747); //potenz, exponent, modulo
    cout << remainder << endl;   //print remainder

}