Write a program (with well written comments and explanations) to implement the b

Question

Write a program (with well written comments and explanations) to implement the binary modular exponentiation algorithm in Section 4.2. The program prompts the user for base 10 integers: b, n & m. The program calculates b n mod m. A student may choose one of the languages below for this assignment.

Java: The Java program needs to accommodate 64-bit computation (e.g. 64-bit divisor m), but it must use primitive data types only, e.g., long.

C++: The C++ program needs to accommodate 64-bit computation too (e.g. 64-bit divisor m), and it must use primitive data types only, e.g., long

Explanation / Answer

c++ program for binarymodular exponential

#include <bits/stdc++.h>

using namespace std;

int BinaryModularExponentiation(int b, int n, int m) //Iterative Function to calculate (b^n)%m
{
int ans = 1; // Initialize answer
b = b % m; // Update b if it is more than or equal to n

while (n > 0)
{
if (n & 1)// If n is odd, (& is a and operator bit wise ) multiply b with answer
ans = (ans*b) % m;

// n must be even now
n = n>>1; // n = n/2
b = (b*b) % m;
}
return ans; //return answer
}

// Main program to find BinaryModularExponentiation functions
int main()
{
int b; // base number
cout<<"Enter value of b"<<endl;
cin>>b;
int n; // power number
cout<<"Enter value of n"<<endl;
cin>>n;
int m; //mod number
cout<<"Enter value of m"<<endl;
cin>>m;
cout<<BinaryModularExponentiation(b, n, m); //call the function to find the result
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.