Residue Number System

To write "real" cryptography, you've gotta be aware of RNS. A naive implementation of cryptographic schemes, which all rely on modular arithmetic on rather large numbers (and typically with moduli other than native powers of 2), is going to be ridiculously slow without such optimizations.

Thanks to the Chinese Remainder Theorem, given any relatively prime moduli $p_1,\ldots,p_n$, for all $x \in {0, \ldots, P-1}$ where $P = \prod p_i$, there exists a unique representation $x = [x_i]$ where $x_i = x \mod p_i$. The $x_i$ are called the residues of $x$.

We can make a signed RNS by designating $X < P/2$ as positive and $X \ge P/2$ as negative. The complement $X^C$ of $X$ is $P - X \mod P$. Then subtraction is simply $X - Y = X + Y^C$.