Question

Use Recursive Algorithm to compute 5^23 Mod 8

Answer 1

Answer :

5

Explanation :

Given three numbers a, b and c, we need to find (a^b) % c

if b is even:
(a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c ? this suggests divide and conquer
if b is odd:
(a ^ b) % c = (a * (a ^( b-1))%c

Here the C++ program

// Recursive C++ program to compute modular power 
#include <bits/stdc++.h> 
using namespace std; 

int exponentMod(int A, int B, int C) 
{ 
        // Base cases 
        if (A == 0) 
                return 0; 
        if (B == 0) 
                return 1; 

        // If B is even 
        long y; 
        if (B % 2 == 0) { 
                y = exponentMod(A, B / 2, C); 
                y = (y * y) % C; 
        } 

        // If B is odd 
        else { 
                y = A % C; 
                y = (y * exponentMod(A, B - 1, C) % C) % C; 
        } 

        return (int)((y + C) % C); 
} 

// Driver code 
int main() 
{ 
        int A = 5, B = 23, C = 8; 
        cout << "Power is " << exponentMod(A, B, C); 
        return 0; 
} 

// This code is contributed by SHUBHAMSINGH10