I've spent some time looking at various algorithms used for square-and-multiply techniques and I've found one that makes more sense to me than others. To put it to use, I am trying to compute the following example:
Compute (31^39 mod 773).
Let a = 31, b = 39.
So the first step is to convert 39 to binary:
39 = 100111
Now, we look at each bit using the following rules:
If we encounter a 0, we square a.
If we encounter a 1, we square a, then multiply by a.
Using these rules, the work looks like so:
Bit ------- Work
1 Starts equation with number
0 31
0 (31^2)
1 ((31^2)^2 * 31)
1 (((31^2)^2*31)^2 *31)
1 (((((31^2)^2*31)^2*31)^2*31)
A side note, I'm not exactly clear on how the first 1 we encounter starts the equation with the number, and why it's blank initially but when we square it (first 0), we get our number.
I'm not sure where to go from here. I understand that what we've just done is break 31^39 down into a much more manageable number, but I don't see how the following helps us compute what we want (31^39 mod 773).
Brian and John, that makes complete sense, awesome, thank you! I went ahead and did the computations that looked liked this:
961 mod 773 = 188
188^2 mod 773 = 559
(559*31)^2 mod 773 = 747
(747*31)^2 mod 773 = 316
(316*31) mod 773 = 520
Thus, 31^39 mod 773 = 520.
Best Answer
It helps because
$$ ab \bmod c = (a \bmod c)(b \bmod c) \bmod c $$
In particular,
$$ (a^m)^n \bmod c = (a^m \bmod c)^n \bmod c $$
Therefore, after each step, you can take the intermediate result modulo $773$, thereby dealing with relatively small numbers (numbers always smaller than $773^2$), instead of constructing a very large number like $31^{39}$, and then taking the result modulo $773$.