How can I exploit the structure of the secp256k1 prime for fast arithmetic?

Question

I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ (a Mersenne prime).

I'm starting with building a circuit to do the modular reduction, I know about Barret's and Montgomery's algorithm, but I have been reading in several guides that because of the $2^n - c$ form, as well as it being a Mersenne prime that there are simpler ways to do the modulo reduction.

But I'm getting stuck on understanding the actual logic underneath this, I was wondering if any one have any good example or pointers to understand how to do this modulo operation a bit better?

There was a similar question here (except I'm doing this on FPGA not CPU, so the word size is irrelevant) but I don't totally understand the answers reply, so even just some helpful comments explaining the same thing would be a huge help. Fast modular reduction

This paper also has a fast implementation on page 7 (http://cse.iitkgp.ac.in/~debdeep/osscrypto/psec/downloads/PSEC-KEM_prime.pdf) which looks like it came from one of these optimizations above, but I would like to try understand how to get there myself.

Answer 1

Let $p = 2^n - c$. Then $2^n - c \equiv 0 \pmod p$, so $2^n \equiv c \pmod p$. Suppose you have an integer $$x = 2^n x_{\mathrm{hi}} + x_{\mathrm{lo}}.$$ Then $$x \equiv c\cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$ In other words, you can compute a reduction step by shift/multiply/add: shift right by $n$, multiply by $c$, and add to the low $n$ bits.

The best case is when $c = 1$, so $p$ is a Mersenne prime: then you can skip the multiplication altogether. But you can generalize this further for $p = 2^n - 2^m - d$, since $2^n \equiv 2^m + d \pmod p$, so $$2^n x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + d \cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$ That is, you can compute a reduction step by an $n$-bit shift, an $m$-bit shift, a multiply by $d$, and two adds.

Similarly, if $p = 2^{2m} - 2^m - 1$, like Ed448-Goldilocks uses, then you can compute a reduction step $$2^{2m} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + x_{\mathrm{hi}} + x_{\mathrm{lo}}$$ with two $n$-bit shifts and two additions.

Obviously, you can always write any modulus as a sum of powers of two; the more terms there are, the more costly the reduction step is to write as a series of shifts and adds. In software implementations, at some point it may be faster to use the CPU's multiplier than your own shift-and-add steps. For instance, in secp256k1, I'd guess that it is fastest to write it as $2^{256} - 2^{32} - 977$ if you can take advantage of a CPU's 32x32->64-bit multiplier, but you should consult libsecp256k1 for the state of the art in arithmetic modulo this prime.