[Math] Intuition behind successive squaring.

exponentiationmodular arithmeticnumber theory

I was looking at the successive squaring method used commonly in modular exponentiation problems and was wondering why we are able to square the remainder of successive powers of a number. For example for $7^{327}$ mod $853$:

$7^1 \equiv$ mod $853$

$7^2 \equiv$ $49$ mod $853$ $= 49$

$7^4 \equiv$ $49^2$ mod $853$ $= 695$

$7^8 \equiv$ $695^2$ mod $853$ $= 227$

$…$

$7^{256} \equiv$ $628^2$ mod $853$ $= 298$

During this operation, why is that we square the remainder and how do we know that doing so will relate to the final answer? I'm struggling to understand the intuition behind this strategy and why this actually works.

Best Answer

You are trying to arrive at the answer with as little computation as possible. You could have arrived to the answer by multiplying $7 \mod{853}$ to itself $327$ times. But that will take forever.

Now, note that any integer ($327$ for example) can be expressed in binary. For example, $327 = 101000111_{2}$. This means that $327 = 1 + 2 + 4 + 64 + 256$.

If you somehow had the values of $7^1, 7^2, 7^4, 7^{64}, 7^{256} \mod {853}$ then multiplying them all together gives you $7^{1 + 2 + 4 + 64 + 256} \equiv 7^{327} \mod {853}$.

And guess what, you can obtain ALL these values by squaring until you get to $7^{256}$. That's just eight squarings (and four multiplications to actually find $7^{327} \mod {853}$). That is much more efficient than multiplying something $327$ times.

Related Question