# Implementation of modular arithmetic?

In FIPS 186-3 appendix D.2 "implementation of Modular Arithmetic", they show shortcuts for solving $$B = A \mod m$$

for select Curves.

How would you go about determining a valid short cuts for the various curves? If I wanted to practice on using a small finite field (e.g. 23, 31) because it's something that could be solved by hand. And I wanted to use one of the mentioned shortcuts, how would I go about deriving it?

As a brief summary, consider a prime: $$p = \sum_{i=0}^{k} b_i 2^{iw}$$ where each $b_i$ is either $0$, $1$ or $-1$, and $w$ is your "word size" (typically $w = 32$ or $64$ will yield the best results on usual computers). You also want $b_0 \neq 0$ ($p$ must be prime, so in particular it must be odd) and $b_k = 1$: the prime value is close to $2^{wk}$. To make things even easier to implement, make sure that $p$ is slightly below $2^{wk}$ rather than slightly higher, meaning that the highest non-zero $b_i$ (for $i < k$) has value $-1$.
With such a prime, modular reduction is easy because, modulo $p$, you have: $$2^{wk} = \sum_{i=0}^{k-1} -b_i 2^{iw} \pmod p$$ from which you can infer: $$-x 2^{w(k+j)} = \sum_{i=0}^{k-1} b_i x 2^{w(i+j)} \pmod p$$ for all integers $x$ and $j$. Therefore, if you have a $n$-word value $X$ (with $n > k$): $$X = \sum_{i=0}^{n-1} x_i 2^{wi} \mathrm{\ \ \ \ \ \ where\ } 0 \leq x_i < 2^w$$ then you can compute the value $X'$: $$X' = X - x_{n-1} 2^{w(n-1)} + \sum_{i=0}^{k-1} b_i x_{n-1} 2^{w(n-1-k+i)}$$ This addition is easily computed because all the $b_i$ are $0$, $1$ or $-1$, so this amounts to adding or subtracting word $x_{n-1}$ to some other, lower words. With the relation above, you have $X' = X \pmod p$. But $X'$ now consists of $n-1$ words. So, with a few addition and subtractions, you have removed one word from your problem. Iterate.
Whether Solinas primes really give that much an advantage over a random prime (with Montgomery multiplication) is disputed. It depends on the implementation architecture. It has also been argued that choosing $p = 2^m - z$ for a small $z$ yields more efficient computations. As for all performance things, there is no absolute answer; it must be tried and measured, and any new language, compiler, processor version or architecture can change the answers.
• Suggestion: "the highest non-zero $b_i$ (for $i<k$) has value $−1$" could be changed to "$b_i=-1$ for the highest $i<k$ for which $b_i\ne0$". Or maybe I could make such minor edits? – fgrieu Jan 18 '14 at 6:04