# Number Theory: Exponentiation with Fast Powering and Montgomery Ladder

## 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.