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

Answer:

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;

}