mieardjoune/RNS · VHDL modular adder, modular multiplier, and CRT-based residue-to-binary conversion, verified against a Python golden model · VHDL, Python
Wide modular arithmetic is where straightforward hardware design goes to die. Add two 256-bit numbers mod a 256-bit prime and you’re carrying a single ripple across the whole width, one bit’s delay compounding into the next, all the way down the chain. A Residue Number System sidesteps the chain entirely: instead of one wide number, you carry a tuple of small residues, one per modulus, and every operation on that tuple happens independently, in parallel, on channels that never need to know what the others are doing.
What CRT is actually buying you#
Pick a set of pairwise-coprime moduli, and the Chinese Remainder Theorem guarantees any integer below their product has exactly one representation as a tuple of residues, and that tuple is reversible. This repo uses 43 of them, 3 through 191 plus 256, whose product is a 257-bit number, large enough to represent anything modulo the NIST P-256 / secp256r1 prime. Addition and multiplication on the tuple are just addition and multiplication on each residue independently: no borrow, no carry, no cross-channel dependency, and every channel fits in 8 bits.
Where this actually shows up#
RNS isn’t a novelty. Public-key crypto accelerators lean on it for exactly this reason, elliptic-curve point arithmetic is dominated by modular multiplication over a fixed prime, and RNS turns one slow wide multiplier into many fast narrow ones running in lockstep. DSP pipelines use it for the same reason on the multiply-accumulate side. It also buys you a security property for free: a fault injected into one residue channel doesn’t propagate into the others, which matters when the thing you’re protecting is a private key.
ModAdder: two carry chains, not one#
ModAdder computes (A + B) mod P for 8-bit operands using two CARRY4 chains in parallel instead of a compare-then-subtract sequence. One chain computes the plain sum; the other computes the sum minus P at the same time, using the same carry-lookahead structure fed with P’s complement. The final carry-out of the second chain tells you which result was actually valid, and a mux picks it. Both results exist before you know which one you need, so there’s no serial “compute sum, check overflow, maybe subtract” penalty, the conditional subtraction happens for free, in parallel with the addition it might correct.
ModMultiplier: shift-and-add, reduced every step#
ModMultiplier builds (A * B) mod P on top of ModAdder: a shift-and-add multiplier that reduces modulo P after every partial product instead of accumulating a wide product and reducing once at the end. That keeps every intermediate value inside the same 8-bit modulus width the whole way through, which is the point, nothing in this design ever needs to be wider than one residue.
ModToNum: turning 43 residues back into one number#
Going back the other way is the expensive part. ModToNum takes all 43 residues and reconstructs the original 257-bit number via CRT: each residue is mapped through a per-modulus lookup table (MTN_IN.vhd) to its CRT weight, and the 43 weighted terms are summed by a wide adder tree (NUMADDER.vhd). The lookup tables aren’t hand-derived, they’re generated directly from the same constants the verification suite checks against, so the hardware and the math can’t quietly drift apart.
Trusting the constants#
verification/ is a pure-Python golden model of the same arithmetic, mod_add, mod_mul, and a CRT-based residues_to_number, checked against brute-force computation and against the exact vectors the VHDL testbenches use. The lookup-table generator reproduces every constant in MTN_IN.vhd, all 43 moduli, byte for byte. If the tables in the repo and the tables this script produces ever disagree, that’s a bug, not a rounding difference.
Running it#
git clone https://github.com/mieardjoune/RNS.git
cd RNS/verification
pip install -r requirements.txt
pytestApache 2.0 licensed.