1

I know that the rule in maths for modulus is this:

ab mod n =(a mod n ) (b mod n) mod n

I have found the following code for computing the modular exponentiation:

pow(base,exponent,modulus){
 if (exponent==0) return 1;
 else {
  newexp=pow((base*base)%modulus,exponent/2,modulus)
  if (exponent%2 != 0){
    return (base*newexp)%modulus;
      }
  else return (newexp%modulus);
  }

However, I do not understand how this code relates to the theory and why it produces a correct result. Can someone explain me how it implements the theory?

  • please don't cross-post: stackoverflow.com/questions/47486857/… "Cross-posting is frowned upon as it leads to fragmented answers splattered all over the network..." – gnat Nov 25 '17 at 17:31
  • a^(2b+1) = a(a^2b) = a((a^2)^b). Take mod n of each factor. Repeat dividing the exponent by 2 until it's trivial. – Sjoerd Nov 25 '17 at 17:32
  • @gnat i posted because nobody was answering in stack overflow , anyway since someone replied here , i delete the question on stack overflow. Thanks though , cause i didn't know i couldn't do that – maverick98 Nov 25 '17 at 17:34
  • 1
    This question is not out of scope. This question asks for a justification why the exposed algorithm is correct. It's not a question about debugging. – Christophe Nov 25 '17 at 18:20
3

Let's look how this equality

ab mod n =(a mod n ) (b mod n) mod n. 

explains your algorithm.

The whole trick is to think about the three possibilities for exponent: it can be null, if can be even or it can be odd.

If exponent is 0, it's easy: any number raised to the power of exponent 0 is 1. This is your first return statement.

If exponent is even, then exponent%2 is 0. This means that you can write the exponent as 2*k, where k is exponent/2 :

pow(a,exponent,n) = a^exponent mod n 
                  = a^(2*k) mod n 
                  = (a^2)^k mod n 
                  = (a*a)^k mod n
                  = pow (a*a, k, n)
                  = pow (a*a, exponent/2, n)
                  = newexp  

As this expression is modulo n, applying modulo n once more will not change it,, so it's the same as newexp % n. Here you have the explanation for your last return statement.

If exponent is odd, then exponent%2 is 1. This means that you can write the exponent as 2*k+1, where k is exponent/2 (integer division):

pow(a,exponent,n) = a^exponent mod n 
                  = a^(2*k+1) mod n 
                  = (a^(2k)*a) mod n
                  = (a^(2k) mod n) * (a mod n) mod n
                  = ((a^2)^k mod n) * (a mod n) mod n
                  = ((a*a)^k mod n) * (a mod n) mod n
                  = pow (a*a, k, n) * (a mod n) mod n 

Because pow(a*a, k, n) is a number modulo n, we know that:

pow(a*a, k, n) mod n = pow(a*a, k, n) 

So we can continue our equality:

pow(a,exponent,n) = pow (a*a, k, n) * (a mod n) mod n    
                  = (pow (a*a, k, n) mod n) * (a mod n) mod n
                  = (a*pow (a*a, k, n)) mod n
                  = (a*pow (a*a, exponent/2, n)) mod n
                  = (a*newexp) mod n

And here you have the explanation for the second return statement.

  • Just when i understood it myself , you answered me , but your explanation is very good. Anyway , i think another explanation is this : it uses the property (A)^B mod C= ((A mod C)^B) mod C example: if i have an even exponent : 9^6 then it calls (9^2 mod 6) ^3 mod 6 and it breaks it down again because 2 is even again 9^2 mod 6 = (9 mod 6)(9 mod 6) mod 6 – maverick98 Nov 25 '17 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.