Speed up modular exponentation with fixed base and modulus

Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed?

https://www.imperialviolet.org/2013/05/10/fastercurve25519.html

Just to mention: it can speed up SRP hashes bruteforce, which is calculated as $v = g^x \mod N$ where $x = hash(username, salt, password)$

-
Rereading my answer, I have to say that Adam's blog you've linked to provides a better explanation. Perhaps it would be easier to try and help you understand that: What did you have trouble understanding? – figlesquidge Nov 26 '13 at 18:13
I want to know this "How big is the gain and what resources are needed?" The explanation in the blog is too big for fast understanding. – Smit Johnth Nov 26 '13 at 18:59

One obvious way is to precompute values $a^{k_1} \bmod N$, $a^{k_2} \bmod N$, ...,$a^{k_i} \bmod N$, and (depending on the value of $x$) multiply together the appropriate elements.

To take a simple example, if we precompute $a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N$, and (based on the value of $x$ in binary, multiply the appropriate elements together); this gives a method which takes an average of $1/2 log_2 N$ multiplies, which is an obvious improvement over what you can do without any precomputation.

The paper gives a slightly more aggressive example (treating $x$ as a base 16 rather than a base 2 number).

However, you can do even better: see this paper for a survey of the various possibilities.

One note: if you are performing operations on an Elliptic Curve (that is, doing a point addition rather than a modular multiplication), then the operation of computing the inverse of an element is cheap; even though the cited paper doesn't cover that case, that can be used to reduce the number of operations even further.

-
AFAIU it's not $1/2 log_2 N$ but $\mathrm{pop}(x)$ where $\mathrm{pop}(x)$ is the number of $1$ bits (Hamming weight). Am I right? – Smit Johnth Nov 26 '13 at 19:06
I meant dependence between x and calculation time. – Smit Johnth Nov 26 '13 at 19:09
@SmitJohnth: yes, it is $pop(x)$; that's why I said "average" (because the average of $pop(x)$ is $1/2\log_2(x)$ – poncho Nov 26 '13 at 19:09
Ah ok. But normally it's $1,5 log2(x)$. NOt a big gain. – Smit Johnth Nov 26 '13 at 19:11
@poncho: Sorry, didn't realise you'd replied when i deleted my comment. rest of world: I was unsure as to which was 'more' aggressive. – figlesquidge Nov 26 '13 at 19:13

In brief: If you know $(a,N)$, you can speed the computation up by precomputing some of the powers of $a$.

Let $x=x_n\dots x_1x_0=\sum_{i=0}^n x_i 2^i$ be the binary expansion of $x$, and let $a_j=a^{2^j}\pmod N$.

Very naively: $$a^x \pmod N = \overbrace{a*(a*(a*\dots*(a))\dots))}^{\text{x terms}}$$ This requires $\theta(x)$ multiplications.

Traditional Square and Multiply: $$a^x \pmod N = a^{x_n \dots x_0} = a^{2^n x_n+ \dots+ x_0} =(a^{2^n})^{x_n} (a^{2^{n-1}})^{x_{n-1}} \dots a^{2^0})^{x_n} =\prod_{i=0}^n a_i^{x_i}$$ So, to use this for efficient multiplication, we maintain a product value $y$, and exponentiation variable $e$ - initialised with $(y,e)=(1,a)$. Then, we simply continue to square $e$, multiplying $y$ by $e$ each time we reach some power $a^{2^j}$ for which $x_j= 1$. How much work does this require? Well, we must calculate $n=\log_2(x)$ multiplications to calculate the $a_j$, and then on average $n/2$ multiplications to calculate $a^x$ (where we assume that an "average" value of $x$ has half it's bits set), and at most $n$ multiplications. Total? $2n$ worst case, $\frac{3}{2}n$ on average.

Precomputational Optimisations of Square and Multiply

Calculating each $a_j=a^{2^j}\pmod N$ in advance, when we calculate $a^x$ we only need to do the (at most) $n$ multiplications. That is, we do not need to do any exponentiations at all. However, if $x$ may be very large, this will involve storing a large amount of data, but by storing some subset of these $j$ we can reduce the number of exponentiations required to reach the remaining values. Moreover, if one so wished this could store values such as $b=a_4*a_2$, which would reduce the online cost of calculating $a^{1010b}$ to the cost of looking up $b=a^{1010b}$.

Deciding a balance for this trade-off provides an interesting question, since at some point storing too many powers becomes unreasonable. For example, it would be possible to precompute and store $a^x\pmod N$ for all $x\in\{0,\dots,2^t\}$. This would reduce calculating $a^x$ to the look-up cost, but such a table would have size $\theta(2^t)$, which may well be impractically large.

-
Sorry, what is θ(x)? – Smit Johnth Nov 26 '13 at 19:07
Maybe I've used bad notation, but when I was taught asymptotics $\theta(\cdot)$ was the version for 'grows like' (contrasting to $O(\cdot)$ for 'upper bounded by' which need not be anywhere near tight). – figlesquidge Nov 26 '13 at 19:08
The simpliest lookup method (table for every $2^n$) give 3x speedup, compared to this, every $x$ speed gain results in $2^x$ table growth (e.g. 8x speed gain needs 256 times bigger table), right? – Smit Johnth Nov 27 '13 at 14:06
For 3x speedup (precomputing $a^{2^n}$, online calculation of $a^x$), the table will grow as $\log(x)$, since we need to store a value of $a_j$ for each bit in the length of $x$. I'm not sure I understand the second half of your question [sorry :( ] – figlesquidge Nov 27 '13 at 14:29
I meant speedup compared to the table for $a^{2^n}$ – Smit Johnth Nov 27 '13 at 14:32