c++ square and multiply algorithm
#include <iostream>
// Function to calculate (base^exponent) % modulus using square and multiply algorithm
long long squareAndMultiply(long long base, long long exponent, long long modulus) {
long long result = 1;
// Convert exponent to binary
while (exponent > 0) {
// If the current bit of the exponent is 1, multiply the result with base % modulus
if (exponent % 2 == 1) {
result = (result * base) % modulus;
}
// Square the base and update the exponent by dividing it by 2
base = (base * base) % modulus;
exponent /= 2;
}
return result;
}
int main() {
long long base, exponent, modulus;
std::cout << "Enter base: ";
std::cin >> base;
std::cout << "Enter exponent: ";
std::cin >> exponent;
std::cout << "Enter modulus: ";
std::cin >> modulus;
long long result = squareAndMultiply(base, exponent, modulus);
std::cout << "Result: " << result << std::endl;
return 0;
}
Explanation:
- squareAndMultiply
function takes three parameters: base
, exponent
, and modulus
and returns (base^exponent) % modulus
using the square and multiply algorithm.
- Initialize result
to 1.
- Convert the exponent
to its binary representation.
- While the exponent is greater than 0:
- If the current bit of the exponent is 1:
- Multiply result
by base
and take the modulus with modulus
.
- Square the base
and update the exponent
by dividing it by 2.
- Return the result
.
- In main
function:
- Input base
, exponent
, and modulus
from the user.
- Call squareAndMultiply
function with the provided inputs.
- Display the computed result.