I'm having difficulty understanding the Square and Multiply algorithm.
As you can see below, we are trying to compute Y = x ^d (mod N) where x=4 and d=12, which is 1100 in binary. There is apparently an efficient way in computing this on a computer called the Square and Multiply algorithm.
My basic understanding is you first convert the exponent to binary. Then, depending on whether you get a 0 or 1 you square or (square and multiply).
But I don't understand why the answer is 1.
Why do you start by squaring 4 and then multiply by 4 in the first round, but in the 2nd round you square (-6) but never multiply it?
I guess I'm a little confused how the binary 0s and 1s relate to whether you square or multiply.
Would appreciate all / any advise.
Best Answer
There are several versions of this algorithm. Yours appears to involve the following steps:
$12=1100_{\text{two}}=2^3+2^2=(2+1)\cdot2^2$, so
$$4^{12}=4^{(2+1)\cdot2^2}=\left(4^{2+1}\right)^{2^2}=\left(4^2\cdot4^1\right)^{2^2}=(16\cdot4)^{2^2}=64^{2^2}\;.$$
Now reduce modulo $35$ before continuing: $64\equiv-6\pmod{35}$, so $4^{12}\equiv(-6)^{2^2}\pmod{35}$. Now
$$(-6)^{2^2}=(-6)^{2\cdot2}=\left((-6)^2\right)^2=36^2\;,$$ and again we reduce modulo $35$ before continuing: $36\equiv 1\pmod{35}$, so $4^{12}\equiv1^2\pmod{35}$. Finally, $1^2=1$, and we have simply $4^{12}\equiv1\pmod{35}$.
In terms of the bits of the exponent this procedure does boil down to squaring and multiplying for a $1$ and just squaring for a $0$ if you ignore the leading $1$:
$$\underbrace{\text{square and multiply}}_1\to\underbrace{\text{square}}_0\to\underbrace{\text{square}}_0\;.$$
If you had the exponent $10$ instead, whose binary representation is $1010_{\text{two}}$, you’d be working with
$$4^{10}=4^{5\cdot2}=4^{(2^2+1)\cdot2}=\left(4^{2^2}\cdot4\right)^2=\left(\left(4^2\right)^2\cdot4\right)^2\;,$$
which breaks down as
$$\underbrace{\text{square}}_0\to\underbrace{\text{square and multiply}}_1\to\underbrace{\text{square}}_0\;.$$
As Trevor Wilson points out in his answer, the leading $1$ is ignored because the real starting point of the calculation is $1$, and squaring $1$ and multiplying by the base always simply gives you the base (here $4$). Thus, you might as well start with the base and ignore the leading bit of the exponent.
Another version of the algorithm would reverse the calculation, squaring when the exponent is even, and multiplying and squaring when the exponent is odd:
$$\begin{align*} 4^{12}&=4^{2\cdot6}=\left(4^2\right)^6\\ &=16^6=16^{2\cdot3}=\left(16^2\right)^3\\ &=256^3\equiv11^3\pmod{35}\\ &\equiv 11\cdot11^2\pmod{35}\\ &\equiv11\cdot121\pmod{35}\\ &\equiv11\cdot16\pmod{35}\\ &\equiv176\pmod{35}\\ &\equiv1\pmod{35}\;. \end{align*}$$
This is in effect processing the exponent in binary from right to left instead of from left to right.