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)$
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.