How do you know when you square/multiply or just square when performing "Square and Multpily" algorithm?

Question

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.

Answer 1

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.

Answer 2

The square-and-multiply method is based on the repeated application of two simple principles:

1. $x^{2n} = \left(x^n\right)^2$
2. $x^{2n+1} = x\cdot\left(x^n\right)^2$

Between them, these allow you to compute $x^k$ as long as you know $\displaystyle x^{\lfloor\frac{k}{2}\rfloor}$. Using them repeatedly allows you to compute $x^d$ for any $d$. To take your example (with $x=4, d=12$), and working backwards to see why we need to build the chain we do:

• We could compute $x^{12}$ if only we knew $x^6$...
• And we could compute $x^6$ if only we knew $x^3$...
• ...and we could compute $x^3$ if only we knew $x^1$...
• ...but we do know $x^1$ - it's just $x$! (i.e., $4$).
• So since we know that $x^1=4$, we know that $x^3=x\cdot \left(x^1\right)^2 = 4\cdot\left(4^2\right) = 4\cdot 16 = 64\equiv 29\pmod{35}$
• And since we know that $x^3\equiv 29\pmod{35}$, we have $x^6 = \left(x^3\right)^2\equiv29^2\equiv841\equiv1\pmod{35}$
• Finally, since we know $x^6\equiv 1\pmod{35}$, we get $x^{12} = \left(x^6\right)^2\equiv1^2\equiv1\pod{35}$.

Answer 3

You are correct that you should square and then multiply when you get a "1", and square when you get a "0" (starting from the left.) However, instead of starting with $x$ you should start with the multiplicative identity, 1. So we get \begin{align*} 1^2 * 4 &\equiv 4\\ 4^2*4 &\equiv -6\\ (-6)^2 &\equiv 1\\ 1^2 &\equiv 1 \equiv Y. \end{align*} What the quoted solution does is to skip the first step and start with $x$ instead of 1. That also works, because the leftmost binary digit is always a "1" (assuming the binary representation has no leading zeroes, e.g. not "01100") and so the output of the first step is always $x$. I hope this way is less confusing, even though it is slightly more work.

Answer 4

Do you know how to convert a number from decimal to binary? You divide the number by 2 repeatedly until reaching zero. The remainder of each step is a digit of your answer.

$$12=2(6)+0$$ $$6=2(3)+0$$ $$3=2(1)+1$$ $$1=2(0)+1$$

Therefore, $12$ in binary is $1100$. Now your algorithm uses this in reverse.

$$x^3=x^{2(1)+1}=(x^1)^2\times x$$ $$x^6=x^{2(3)+0}=(x^3)^2\times x^0=(x^3)^2$$ $$x^{12}=x^{2(6)}=(x^6)^2$$