CODEWITHSUNDEEP
c++moduloexponentiation
Qbik
Qbik

Reputation: 6147

Modular exponentiation in C++

Something is wrong in my code for modular exponentiation and I can't spot the problem despite of writing it three times when using two different sources of pseudocode. I've read other questions about modular exponentiation in C++ on SE but that didn't help me. Here is my last code, written by simpler but less optimal way I think :

#include<iostream>
using namespace std;

// base ^ exponent mod modulus 
unsigned mulmod1(unsigned base, unsigned exponent, unsigned modulus) {
    int result = 1;
    while(exponent > 0){
        if(exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
  return result;
}

int main(){

//9688563^45896 mod 71 = 30
//12^53 mod 7 = 3

cout<<mulmod1(9688563,45896 ,71)<<"\n";   //gives 10 instead of 30
cout<<mulmod1(12,53,7)<<"\n";             //gives correct answer 3

return 0;
}

Upvotes: 0

Views: 1156

Answers (1)

us2012
us2012

Reputation: 16253

Sanitize the inputs to your function mulmod1! unsigned cannot hold 9688563*9688563. If you do this right, you 'only' need a data type that can hold modulus * modulus (and your input numbers, of course) to perform modular exponentiation correctly.

Upvotes: 4

Related Questions