The code has to be in C++. Thank you. Write a program where vou implement Modula
ID: 3601466 • Letter: T
Question
The code has to be in C++. Thank you.
Write a program where vou implement Modular Exponentiation (ME) using the square and multiply approach as a function which is called in main. ME calculates a^k mod n. The program should get values for a, k and n from the user. This code requires two steps. First k must be converted to a binary representation K consisting of a list of 0s and 1s. Second, Modular Exponentiation must be performed using a, n and KIl as arguments procedure BinaryK(k) K = empty list //hint: make K a vector tmp k while tmp >0 add y mod 2 to K //hint: use pushback tmp (tmp-K[i])/2 return K procedure ModularExpo(a, K, n) ifn= 1 return 0 return b if K[0]-1 for i = l to length(K)-1 A =A*A mod n ifK[i] = 1 b- A*b mod n return bExplanation / Answer
C++ code for above psuedocode
vector<int> BinaryK(int k){
vector<int> bin;
int tmp=k,i=0,rem;
while(tmp>0){
rem = tmp%2;
bin.push_back(rem);
tmp = (tmp-bin[i])/2;
i++;
}
return bin;
}
double modularExpo(int a, vector<int> K, int n){
double b =1;
int A=a,i=0;
if(n == 1)
return 0;
if(k == 0)
return b;
if(K[0] == 1)
b = a;
for(i=0; i<K.size(); i++){
A = A*A %n;
if(K[i] == 1)
b = A*b %n
}
return b;
}