2

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 – user289846 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
2

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 – user289846 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