harlock

Stacker Saloon

saloon

Yo, that post is mine, and I'm not a bot. Sorry if it seemed like it. My bad, I probably should  have posted the content instead of just dropping the link to my blog. I'm new to SN.

math

bitcoin

I published a blog post about how the GLV endomorphism works on libsecp256k1

bitdevs

**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 secp256k1

In `secp256k1`, almost every elliptic curve operation requires a **modular inversion** in the finite field (computing $$a^{-1} \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)

If $$p$$ is prime and $$a \not\equiv 0 \pmod p$$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

From this, we can derive the modular inverse directly:

$$a \cdot a^{p-2} \equiv 1 \pmod{p} \implies a^{-1} \equiv a^{p-2} \pmod{p}$$

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

### The 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](https://www.harlock.xyz/the-secp256k1-first-commit-analysis-part-2-modular-inversion-via-fermats-little-theorem)