modular exponentiation algorithm c++

Here is an explanation of the modular exponentiation algorithm in C++:

1. Input: The algorithm takes three parameters: base, exponent, and modulus. The base represents the number to be raised to the power of the exponent, and the modulus is the number by which the result is to be divided.

2. Initialize: Create a variable result and set it to 1. This variable will store the final result of the modular exponentiation calculation.

3. Loop: Start a loop that iterates exponent number of times.

4. Condition: Check if the least significant bit of the exponent is set or not. This can be done by performing a bitwise AND operation (exponent & 1). If the result is 1, it means the bit is set.

5. Update result: If the condition is true, multiply result with base modulo modulus and store the result back in result. This step is performed to keep the result within the range of the modulus.

6. Update base: Square the value of base and store the result back in base. This step is performed to efficiently calculate the next power of base.

7. Update exponent: Right-shift the value of exponent by 1 bit. This step effectively divides the exponent by 2.

8. Repeat: Go back to step 4 and continue the loop until the exponent becomes 0.

9. Output: The final value of result is the modular exponentiation of the base raised to the power of the exponent modulo modulus.

Here is an example implementation of the modular exponentiation algorithm in C++:

int modularExponentiation(int base, int exponent, int modulus) {
    int result = 1;

    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }

    return result;
}

You can use this function by passing the appropriate values for base, exponent, and modulus. The function will return the modular exponentiation result.