Intuition behind successive squaring.

Intuition behind successive squaring.

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 7327 mod 853: 71 equiv mod 853 72 equiv 49 mod 853 49 74 equiv 492 mod 853 695 78 equiv 6952 mod 853 227 ... 7256 equiv 6282 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 Im struggling to understand the intuition behind this strategy and why this actually works.

You are trying to arrive at the answer with as little computation as possible. You could have arrived to the answer by multiplying 7 mod853 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 71, 72, 74, 764, 7256 mod 853 then multiplying them all together gives you 71 2 4 64 256 equiv 7327 mod 853. And guess what, you can obtain ALL these values by squaring until you get to 7256. Thats just eight squarings and four multiplications. That is much more efficient than multiplying something 327 times.