Analysis of secp256k1's first commit: Modular inversion via Fermat's Little Theorem

This is a cross-post from my blog. I'm starting to write more about early Bitcoin implementations, and feedback is very welcome.

Why modular inversion matters in secp256k1Why modular inversion matters in secp256k1

In secp256k1, almost every elliptic curve operation requires a modular inversion in the finite field (computing $a^{-1}\mathrm{mod}p$). This is an expensive operation.

In the very first commit of the library (2013), instead of using the Extended Euclidean Algorithm (which is used today), the code computed the inverse using Fermat's Little Theorem.

Fermat's Little Theorem (intuitive version)Fermat's Little Theorem (intuitive version)

If $p$ is prime and $a\not\equiv 0(\mathrm{mod}p)$, then:

$a^{p-1}\equiv 1(\mathrm{mod}p)$

From this, we can derive the modular inverse directly:

$a\cdot a^{p-2}\equiv 1(\mathrm{mod}p)⟹a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$

So to invert (a), we just need to compute (a^{p-2} \mod p).

The challengeThe challenge

The prime used in secp256k1 is (p = 2^{256} - 2^{32} - 977). This means the exponent (p-2) is enormous. Naïve exponentiation would be far too slow.

The standard solution is binary exponentiation (exponentiation by squaring), which brings the complexity down to (O(\log n)).

This post is a summary.

The full article goes deeper into:

• A more intuitive explanation of Fermat’s Little Theorem
• How binary exponentiation works in practice with examples
• The actual 5-bit addition chain optimization used in the first commit (with code analysis)

Read the full article here:

The secp256k1 first commit analysis part 2: modular inversion via Fermat's Little Theorem