# How does this function for calculating modular exponentiation work ?

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
• 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

Let's look how this equality

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

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