Question

Write a program where you implement Modular Exponentiation (ME) using the square and multiplyapproach as a function which is called in main. ME calculates a^k mod n. The program should get valuesfor a, k and n from the user. This code requires two steps. First k must be converted to a binaryrepresentation K consisting of a list of 0s and 1s. Second, Modular Exponentiation must be performedusing a, n and K[] as arguments.procedureBinaryK(k)K = empty list //hint: make K a vectortmp = ki = 0while tmp > 0add y mod 2 to K //hint: use pushbacktmp = (tmp-K[i])/2i++return KprocedureModularExpo(a, K, n)if n = 1return 0b = 1if k = 0return bA = aif K[0] = 1b = afor i = 1 to length(K)-1A = A*A mod nif K[i] = 1b = A*b mod nreturn b

Answer 1

Step-by-step explanation:

#include <iostream>

#include<vector>

using namespace std;

//calculating k value in binary digits

vector<int> BinaryK(int k){

vector<int> temp;

int r;

while(k!=0)

{

r = k%2; //getting binary value at every step

temp.push_back(r);

k /= 2;

}

return temp;

}

int ModularExpo(int a, vector<int> k, int n){

if(n == 1){ //if denominator is 1

return 0;

}

int b = 1;

bool zeros = std::all_of(k.begin(), k.end(), [](int i) { return i==0; }); //checking denominator is zero vector

if(zeros){

return b;

}

int A = a;

if(k[0] == 1){

b = a;

}

for(int i=0;i<k.size();i++){

A = (A*A) % n;

if(k[i] == 1){

b = (A*b)%n;

}

}

return b;

}

int main(){

//declaring variables

int a,k,n;

//reading variables

cout<<"Reading a: ";

cin>>a;

cout<<"Reading k: ";

cin>>k;

cout<<"Enter n: ";

cin>>n;

//declaring vector

vector<int> vec;

//calling functions

vec = BinaryK(k);

cout<<"Result is: "<<ModularExpo(a,vec,n);

return 0;

}