Modular representation
 Modular representation Let be the set { m1, m2, m3, ... mn} of n integer constants pairwise prime called moduli and let M be the product of these constants, M = m1× m2× m3× ... × mn. Let A be an integer smaller than M. A can be written ( a1½ a2½ a3½....½ an )RNS where ai = A modulo mi. This definition tells how to get the ai from A. On the other hand it is possible to get back A from the ai using another set of precomputed constants { im1, im2, im3, ... imn} called inverse modulo M of the former. A = ½ a1 × im1 + a2 × im2 + a3 × im3 + ..... an × imn ½ modulo M This property is demonstrated by the "Chinese Remainder Theorem". Check whether you are acquainted with this representation by either converting A from decimal to RNS or converting A from RNS to decimal.
 Modular addition Modular addition uses n small adders computing simultaneously all the sums si = ½ ai + bi ½ modulo  mi .

 Adder modulo An adder modulo is an adder followed by a modulo operator, i.e. a conditional subtractor.
 Modular Subtraction Modular subtraction uses n small subtractors computing simultaneously all the differences di = ½ ai + mi  bi ½ modulo  mi .
 Modular Multiplication Modular multiplication uses n small multipliers computing simultaneously all the products pi = ½ ai × bi ½ modulo  mi .

 Conversion into "RNS" The conversion of a binary variable A into "RNS" consists in finding all ai = A modulo mi i.e. the remainders of the division of A by mi. But the division is not the best approach. the rest modulo 2n is immediate, the rest modulo 2n  1 requires only additions, the rest modulo 2n + 1 requires additions and some subtractions. otherwise we resort to the one of the two last expressions with the smallest n. Trees of adders (Wallace trees) reduces A to the sum of two n-bit numbers while respecting the rest modulo mi. The graphical conventions are the same as for partial products reduction.

 Reduction modulo 2n1 The following applet reduces 64 bits into 6 bits whereas preserving the value modulo 63 (63 = 26  1) . At the output, zero has two notations: either '000 000' or '111 111'

 Adder modulo 2n1 The "carry-end-around" adder offers two advantages : it works fine and is simple, and two disadvantages as well : it is slow and difficult to test, both for the same raison i.e. for the value zero there are two stable cases. An adder delivers spontaneously a modulo 2n sum. With a slight modification, the Sklansky's adder with a late carry-in delivers a modulo 2n  1 sum S. if A + B < 2n  1 then S = A + B ; if A + B ³ 2n  1 then S = ½ A + B + 1 ½ modulo 2 n The condition is given by the carry out cn: if cn = 'K' then A + B < 2n  1, if cn = 'P' then A + B = 2n  1, if cn = 'G' then A + B > 2n  1. The "feed-back" signal that controls the "+1" is 'K' if cn = 'K' and 'G' otherwise.
 Multiplier modulo 2n  1 The multiplication modulo 2n  1 of two numbers n-bit each follows 3 steps : production of n2 partial products modulo 2n  1 reduction of this n2 partial products 2n  1 into two numbers of n bits addition of these two numbers modulo 2n  1 with the preceding adder.
 Partial products reduction modulo 2n 1 The reduction of the n2 partial products modulo 2n  1 is similar to fast multiplication reduction and the graphical conventions are preserved.
 Reduction modulo 2n + 1 The following applet reduces 64 bits into 7 bits while preserving the value modulo 65 (65 = 26 + 1) . It is derived from the previous reducer by complementing all the bits with position within 6(2k + 1) and 6(2k + 1) + 5 , k is an integer. The output carry of the terminal adder cannot be fed back in the adder. Instead it must be added to the result, yielding another 7-bit number.
 Modulo 2n +1 adder We now can use an adder modulo 2n + 1, if only to replace the final carry-propagate addition of the above reduction.
 Multiplier modulo 2n + 1 A number modulo 2n-1 + 1 fits in n bits or the sum of two numbers with n1 bits each. The generation of the n2 partial products modulo 2n-1 + 1 adds a bias equal to 2n + 2n-1 n  2. The partial product reduction compensates for the bias .
 Partial products reduction modulo 2n + 1 The applet reduces (n-1)×(n+1) +1 bits into two numbers n1 bits each modulo 2n-1+ 1. These two output numbers should be added with the aforementioned adder modulo circuit. This reduction adds another bias equal to n (number of feed-back). The compensation of the two biases modulo 2n-1 + 1 consists merely in adding 5 during the reduction.
 Conversion from "RNS" into mixed-radix system "MRS" The "Mixed Radix System" is a positional number system with weights (1) (m1) (m1m2) (m1m2m3) (m1m2m3.....mn-1 ) . In this system X is written ( z1½ z2½ z3½....½ zn )MRS with 0 £ zi < mi. Note that digit set have the same range as RNS digits, but digits themselves are different. The value of X = z1 + m1 × (z2 + m2 × (z3 + m3 × ( ..... ))).
 Operators library A very comprehensive library for modular arithmetic operators has been developed in "A VHDL Library for Integer and Modular Arithmetic"