Square and Multiply Decoding

217 Views Asked by At

Use the square and multiply method to decode the message 28717160 when $n=77$ and $d=13$. For the letter/number correspondence, use A=1.

I have no idea what the "square and multiply method" is. I have found this resource: https://math.la.asu.edu/~nc/rsa.pdf, but I do not understand how that would help to decode the message.

1

There are 1 best solutions below

1
On

Square and multiply method is just a quicker way to compute $m^d\bmod n$.

To contrast, say you choose to take the power by doing $(m\times m\times \cdots \times m)\bmod n$ or $(\cdots((m\times m\bmod n )\times m\bmod n)\cdots)\times m\bmod n$, you have to perform $d$ multiplications, which is exponential time considering the number of bits (or the length) of $d$.

By using square and multiply method, $m^d \bmod n$ is calculated by first calculating $$\begin{align*} m^2 \bmod n &= m \times m \bmod n\\ m^4 \bmod n &= \left[\left(m^2\bmod n\right)\times\left(m^2\bmod n\right)\right]\bmod n\\ m^8 \bmod n &= \left[\left(m^4\bmod n\right)\times\left(m^4\bmod n\right)\right]\bmod n\\ &\vdots\\ m^{2^{k+1}}\bmod n &= \left[\left(m^{2^k}\bmod n\right)\times\left(m^{2^k}\bmod n\right)\right]\bmod n \end{align*}$$ and then combining the required powers of $m$ using the binary representation of $d$. For example, $d = 33 = 32 + 1$, so $$m^{33} \bmod n = \left[\left(m^{32}\bmod n\right)\times\left(m\bmod n\right)\right]\bmod n$$ The main advantage is speed, as the time complexity is linear, in the order of the number of bits of $d$.