Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

square and multiply algorithm

share|improve this question

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
This is exactly the kind of explanation I needed. Thanks very much Brian. –  user1068636 Dec 19 '12 at 5:44
    
@user1068636: Glad to help; you’re very welcome. –  Brian M. Scott Dec 19 '12 at 5:46

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.

share|improve this answer
    
Hi Trevel - Thanks for this explanation. –  user1068636 Dec 19 '12 at 5:46

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}$.
share|improve this answer

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$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.