Design an algorithm that takes a positive integer N (modulus) and two non-negati

Question

Design an algorithm that takes a positive integer N (modulus) and two non-negative integers x and y, and returns x^y(mod N). (Assume that x, y lessthanorequalto N - 1, and that N, x and y are in base 2 and are represented as vectors of binary digits.) Test your program for N = (1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1). x = [1, 1, 0, 1, 1, 1, 1, 1, 1], y = [0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1] N = [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1], x = [1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1], y = [1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1]

Explanation / Answer

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int base2ToDec(vector <int> b)
{
   int bb=0;
   int pp=b.size()-1;
   for(int i=0;i<b.size();i++)
   {
       bb+=b.at(i)*pow(2,pp);
       pp--;
   }
   return bb;
}

long int evaluate(vector <int> nn, vector <int> xx,vector <int> yy)
{
   long int x=base2ToDec(xx);
   long int y=base2ToDec(yy);
   long int N=base2ToDec(nn);

   return (int)pow(x,y) % N;
}

int main()
{
   int myints[] = {1,1,1,1,1,0,0,0,1,1,1,1,0,1};
vector<int> N(myints, myints + sizeof(myints) / sizeof(int) );
int xx[]={1,1,0,1,1,1,1,1,1};
vector <int> x(xx, xx + sizeof(xx) / sizeof(int) );
int yy[]={0,1,0,1,1,0,0,0,1,1,1,1};
vector <int> y(yy, yy + sizeof(yy) / sizeof(int) );
   int ans=evaluate(N,x,y);
   cout<<endl<<"Answer: "<<ans;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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