R N S       Residue Number System    resources    preliminary /
under construction

Modular Addition

The easiest way to implement two-operand modular addition, for any modulus m,
< a1 + a2 >m
is to perform two additions modulus 2k (with m ≤ 2k). If the result of a1 + a2 exceeds the modulus, by subtracting m we obtain the correct result. To speed-up the operation we can execute in parallel the two operations:
(a1 + a2)     and     (a1 + a2 - m).
If the sign of the three-term addition is negative, it means than the sum (a1 + a2) < m and the modular sum is a1 + a2, otherwise the modular addition is the result of the three-term addition.

The above algorithm can be implemented by the most general architecture shown in Figure 3. Clearly, the modular adder is simplified when:

m = 2k.
In this case a mod 2k addition only requires the sum of the k least-significant bits.
m = 2k-1.
In this case, the mod 2k-1 addition can be implemented with an end-around-carry mod 2k adder.

The scheme of Figure 3 is very general and several methods have been presented to efficiently implement the correction -m [3]. If the latency of the modular addition is not an issue, the algorithm can be implemented serially as in [4].

Figure 3: Architecture of the modular adder.

Resources

Addition Applet

[Home]    < Previous    Next >