Jan 122016
 

It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become extremely large as the exponent increases in value. The following rule provides a great computational advantage when doing modular exponentiation.

The rule for doing exponentiation in modular arithmetic is:

a^b \bmod{c} = ((a \bmod{c})^b) \bmod{c}

This states that if we take an integer a, raise it to an integer power b and calculate the result modulo c we will get the same result as if we had taken a modulo c first, raise it to b, and calculate that product modulo c.

Proof

I’m winging it on this one, but the quotient remainder theorem hasn’t let me down yet, so I am going to start by defining a and b using it:

a = cq_{1} + r_{1} where 0 \leq r_{1} < c this means that a \bmod{c} = r_{1}
b = cq_{2} + r_{2} where 0 \leq r_{2} < c this means that b \bmod{c} = r{2}

This time we will just substitute for a in the left hand side of our exponentiation rule:

a^b \bmod{c} = ((cq_{1} + r_{1})^b) \bmod{c}

The binomial theorem gives us an easy way to expand the binomial we just introduced:

a^b \bmod{c} = [{b \choose 0}(cq_1)^b + {b \choose 1}(cq_1)^{b-1}r_1^1 + ... +  {b \choose {b-1}}(cq_1)^1r_1^{b-1} + {b \choose b}r_1^b] \bmod{c}

Fortunately, because we are taking the result modulo c, we can eliminate any terms in the expanded binomial that contain c, leaving us with:

a^b \bmod{c} = ({b \choose b}r_1^b) \bmod{c}

b choose b is equal to 1, so:

a^b \bmod{c} = r_1^b \bmod{c}

From our definition of a using quotient remainder theorem, r_{1} = a \bmod{c}:

a^b \bmod{c} = ((a \bmod{c})^b) \bmod{c}

And that, as they say, is all she wrote.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)