0

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;
}
Qbik
  • 5,885
  • 14
  • 62
  • 93
  • 3
    Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, and then construct a [minimal test-case](http://sscce.org). – Oliver Charlesworth Mar 03 '13 at 12:53
  • I've added print statements but I it didn't help and now I start to think I don't understand something with idea of modular exponentiation or with C++ itself – Qbik Mar 03 '13 at 12:57
  • You should find the simplest test-case that doesn't work, then add print statements to trace the value of every single variable on every single iteration, and compare them to a manual calculation. As soon as there is a discrepancy, then you have found your bug. – Oliver Charlesworth Mar 03 '13 at 12:57

1 Answers1

4

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.

us2012
  • 16,083
  • 3
  • 46
  • 62
  • unsigned long long also, so I've to try another pseudocode for suitable for bigger numbers – Qbik Mar 03 '13 at 12:59
  • 1
    @Qbik In case it wasn't clear, I was suggesting that you do `base = base % modulus` before doing any calculations on it... – us2012 Mar 03 '13 at 13:00
  • I've just added this, something is still wrong mulmod1(9688563,45896 ,71) gives 20 instead of 30 – Qbik Mar 03 '13 at 13:08
  • 1
    Actually, I think 20 is the correct answer. You can try it in Python: `pow(9688563,45896,71)` yields `20`. See also [here](http://stackoverflow.com/q/5246856/2073257). – Daniel Frey Mar 03 '13 at 13:12