Square-and-Multiply Algorithm

Square-and-Multiply Algorithm is an algorithm used to compute exponentiation, especially for larger numbers, by repeatedly squaring base and multiplying in the ones that are needed to compute the result looking at binary representation of the exponent. The running time# of it is $O(\lg n)$.

Let’s compute $3^{23} \mod 7$ using this algorithm! First, we need to find out the base 2 version or binary representation of the exponent, $23$, which is $10111$. Reading the binary from left to right, we need to compute $3^{1_2}$, $3^{10_2}$, $3^{101_2}$, $3^{1011_2}$, and $3^{10111_2}$ which are $3^1$, $3^2$, $3^5$, $3^{11}$, and $3^{23}$ respectively. Utilising combination of multiplication and/or squaring, we can get the answer without computing a large exponent, but rather based our answer on previously computed result. The following shows the complete step for computing $3^{23} \mod 7$:

$$ \begin{align*} 3^1 &= 3 \mod 7\\ &= 3\\ 3^2 &= 3^1 \cdot 3^1 \mod 7\\ &= 9 \mod 7\\ &= 2\\ 3^5 &= (3^2)^2 \cdot 3^1 \mod 7\\ &= 2^2 \cdot 3^1 \mod 7\\ &= 4 \cdot 3 \mod 7\\ &= 12 \mod 7\\ &= 5\\ 3^{11} &= (3^5)^2 \cdot 3^1 \mod 7\\ &= 5^2 \cdot 3^1 \mod 7\\ &= 25 \cdot 3 \mod 7\\ &= 75 \mod 7\\ &= 5\\ 3^{23} &= (3^{11})^2 \cdot 3^1 \mod 7\\ &= 5^2 \cdot 3^1 \mod 7\\ &= 5 \end{align*} $$

Thus, the computing result for $3^{23} \mod 7$ is $5$.

Links to this page

TAC3121 Chapter 4: Asymmetric (Public-Key) Encryption

Square-and-Multiply Algorithm
Rivest-Shamir-Adleman (RSA)

From here, we could get the public key $pu = \{e, n\}$ and private key $pr = \{d, n\}$. Encryption could be done on message $M$ using the formula $C = M^e \mod n$ where $0 \le M < n$ by using public key $pu$ which is typically done by Square-and-Multiply Algorithm# for efficiency. Decryption could be done on ciphertext $C$ using the formula $M = C^d \mod n$ by using private key $pr$ which is usually done by Chinese Remainder Theorem (CRT)#.

Note: $e$ is usually relatively small or $65537_{10}$ which is $10000000000000001_2$ for easy computation by Square-and-Multiply Algorithm#. That being said, $e$ can’t be either 1 or 2. The former means no encryption is done on $M$ as $M^e = M^1 = M$. The latter will not work due ($d$ not exist) to the nature of Greatest Common Divisor (GCD)# since $GCD(2, \phi(n))$ will always be 2 as $\phi(n) = (p - 1) (q - 1)$ where $p$ and $q$ are primes results in even number. However, if $e$ is too small, it is vulnerable to mathematical attack using Chinese Remainder Theorem (CRT)#.