Repeated squaring techniques

Solution 1:

For the binary method, you compute each of the relevant factors, like $3^{256},3^{64}$, etc., just by using repeated squaring. (Note that you can compute each of the factors you need by just saving them as you compute $3^{256}$.) Then you multiply them together (if they correspond to a $1$ in the binary expansion of the exponent of course). This adds up the exponents, so it all works out.

For the method in your text, you basically are going to step your way up to $3^{383}$ by repeatedly squaring what you have and then possibly multiplying by $3$ again, depending on whether the next exponent in the sequence, going right to left, is even or odd. In this case it turned out that you needed to multiply by $3$ again every single time except the first. This works basically because as you go through your sequence of exponents from right to left, the next number is either double the current number, or double it $+1$.

You can also view the method of your text recursively instead of iteratively. From this standpoint, to compute $3^{383}$ it is enough to compute $3^{191}$, square it and multiply by $3$; to compute $3^{191}$ it is enough to compute $3^{95}$, square it and multiply by $3$; etc.

Both ways are fine. The binary way is a little bit cleaner, because you don't have this case work to do at each iteration depending on whether the next exponent is even or odd, or the analogous case work in the recursive implementation. Accordingly, it would probably be faster on a computer for most inputs because of branch prediction. The way in your text requires a bit less memory (which could potentially matter if your modulus and/or the exponent were much larger). The binary way will require slightly fewer total operations.

Solution 2:

You can get $3^{256}$ from $(3^{64})^4$ The approaches are similar. The difference is where you put in the odd factors. Your text's example computes $3^{23}=3^{11+11+1}=3^{11}3^{11}3$ whereas Khan would compute $3^{23}=3^{16+4+2+1}$ This is a particularly easy example for your text because above $5$ you always have $5 \times 5 \times 3 \equiv 5 \pmod 7$ but that is an accident. On average the Khan approach gives you a few less multiplies, but the difference is small. Use whichever you like.

Solution 3:

Working through a step of your example will show why the book's method works. We have $$\lfloor 383 / 2 \rfloor = 191$$ ($\lfloor x \rfloor$ denotes the floor of $x$). Since $383$ is odd and thus rounding occurred, this implies that $$3^{383} \bmod 7 = 3 (3^{191})^2$$ Thus, if we knew the value of $3^{191} \bmod 7$, then it would be easy to find $3^{383} \bmod 7$ so the next step would be to continue recursively by computing $3^{191} \bmod 7$. Your text is following the same process except that it performs all the divisions and floorings first so that one can start with the smallest exponents first. This doesn't change any of the logic above but does make things more efficient.