Motivation§

We often use exponentiation over finite fields in cryptography, as solving for $a$ given $g, h, n$ in the discrete log problem $g^a \equiv_n h$ is very difficult. However, our exponents are often quite large and computing them through the naïve method of repeated multiplication is not the fastest method asymptotically.

Suppose we wanted to compute $3^{387} \pmod{100}$, in this case we must compute $387$ multiplications of the base $3$ in the naïve method. With fast-powering we can get it down to $\log_2(387) \approx 9$ steps which have at most $2$ multiplications each.

This reduction in the number of steps is doubly important, because naïve integer multiplication in binary is $\mathcal{O}\left(n^2\right)$. In cryptography we work with very large bases and exponents, so these time complexities are very important in terms of practicality. So, using both naïve exponentiation and multiplication, we can expect $\mathcal{O}\left(n^3\right)$ time complexity. We can get better asymptotic times for multiplication using Karatsuba, Toom-k, or fast-fourier transforms for increasingly larger numbers; thusly reducing the asymptotic run-time of the fast-powering approach.

Additionally, we can use a result from Euler’s theorem in certain cases to reduce the exponent before attempting to compute the exponent value.

Fast Powering§

Most texts refer to this method as Exponentiation by squaring instead of fast-powering.

Fast Powering

Suppose for a large $A$ we want to compute $g^A \pmod{N}$, we first want to find the binary expansion of $A$:

$$ A = \sum_{i=0}^{m}A_i2^i = A_0 + A_1\cdot2 + A_2\cdot2^2 + \dots + A_m\cdot2^m $$

Then, for each power of two we compute

$$ \begin{align*} g^{2^0} &\equiv a_0\pmod{N}\\ g^{2^1} &\equiv (a_0)^2 \equiv a_1\pmod{N}\\ g^{2^2} &\equiv (a_1)^2 \equiv a_2\pmod{N}\\ &\mkern.5em\vdots\\ g^{2^m} &\equiv (a_{m-1})^2 \equiv a_m\pmod{N}. \end{align*} $$

Finally, we compute

$$ g^A \equiv \prod_{i=0}^m g^{A_i\cdot 2^i} \equiv g^{A_0} \left(g^2\right)^{A_1}\dots\left(g^{2m}\right)^{A_m} \pmod{N} $$

Fast powering is susceptible to side-channel attacks, i.e. someone can observe the timing of the algorithm to determine the number of squaring and multiplication steps done in order to recover the exponent used in exponentiation.

Montgomery Ladder§

The Montgomery ladder method attempts to mitigate the viability of side-channel attacks by performing a squaring and multiplication at each step.