bitcoin-core / secp256k1

This document explains the modular inverse implementation in the src/modinv*.h files. It is based on the paper "Fast constant-time gcd computation and modular inversion" by Daniel J. Bernstein and Bo-Yin Yang. The references below are for the Date: 2019.04.13 version.

The actual implementation is in C of course, but for demonstration purposes Python3 is used here. Most implementation aspects and optimizations are explained, except those that depend on the specific number representation used in the C code.

It computes the greatest common divisor of an odd integer f and any integer g. Its inner loop keeps rewriting the variables f and g alongside a state variable δ that starts at 1, until g=0 is reached. At that point, |f| gives the GCD. Each of the transitions in the loop is called a "division step" (referred to as divstep in what follows).

Compared to more traditional GCD algorithms, this one has the property of only ever looking at the low-order bits of the variables to decide the next steps, and being easy to make constant-time (in more low-level languages than Python). The δ parameter is necessary to guide the algorithm towards shrinking the numbers' magnitudes without explicitly needing to look at high order bits.

Leave a Comment