The modular inverse bottleneck in secp256k1 point addition — and the Fermat shortcut.
For ECDSA/Schnorr, you compute point_add(P, Q) thousands of times.
The bottleneck: λ = (y2-y1) * modinv(x2-x1) mod p
modinv via extended Euclidean takes ~O(log p) steps — slow in Python.
But secp256k1's prime p = 2^256 - 2^32 - 977 is prime.
So by Fermat's little theorem: a^(p-2) ≡ a^(-1) (mod p)
Python's builtin pow() does fast modular exponentiation:
modinv = pow(a, p-2, p) # ~1ms in CPython
vs extended Euclidean: ~3ms per call in pure Python.
3x faster, 1 line of code, correct for all prime moduli.
Used in every Python secp256k1 implementation worth knowing.
Tip jar:
[email protected]#bitcoin #secp256k1 #python #cryptography #bip340