Modular representation 
Modular representation 
Let be the set { m_{1}, m_{2}, m_{3}, ... m_{n}} of n integer constants pairwise
prime called moduli and let M be the product of these constants, M = m_{1}× m_{2}×
m_{3}× ... × m_{n}. Let A be an integer smaller than M. A can be written ( a_{1}½ a_{2}½ a_{3}½....½ a_{n })_{RNS} where a_{i} = A modulo m_{i}. This definition tells how to get the a_{i} from A. On the other hand it is possible to get back A from the a_{i} using another set of precomputed constants { im_{1}, im_{2}, im_{3}, ... im_{n}} called inverse modulo M of the former. A = ½ a_{1} × im_{1} + a_{2} × im_{2} + a_{3} × im_{3} + ..... a_{n} × im_{n} ½_{ 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 s_{i} = ½ a_{i} + b_{i} ½_{ modulo} m_{i} . 
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 d_{i} = ½ a_{i} + m_{i} – b_{i} ½ _{modulo} m_{i} . 
Modular Multiplication 
Modular multiplication uses n small multipliers computing simultaneously all the products p_{i} = ½ a_{i} × b_{i} ½ _{modulo} m_{i} . 
Conversion into "RNS" 
The conversion of a binary variable A into "RNS" consists in finding all a_{i} = A modulo m_{i} i.e. the remainders of the division of A by m_{i}. But the division is not the best approach.
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 nbit numbers while respecting the rest modulo m_{i}. 
Reduction modulo 2^{n}–1 
The following applet reduces 64 bits into 6 bits whereas preserving the value modulo 63 (63 = 2^{6} – 1) . At the output, zero has two notations: either '000 000' or '111 111' 
Adder modulo 2^{n}–1 
The "carryendaround" 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.
The condition is given by the carry out c_{n}: if c_{n} = 'K' then A + B < 2^{n} – 1, if c_{n} = 'P' then A + B = 2^{n} – 1, if c_{n} = 'G' then A + B > 2^{n} – 1. The "feedback" signal that controls the "+1" is 'K' if c_{n} = 'K' and 'G' otherwise. 
Multiplier modulo 2^{n} – 1 
The multiplication modulo 2^{n} – 1 of two numbers nbit each follows 3 steps :

Partial products reduction modulo 2^{n}– 1 
The reduction of the n^{2 }partial products modulo 2^{n} – 1 is similar to fast multiplication reduction and the graphical conventions are preserved. 
Reduction modulo 2^{n} + 1 
The following applet reduces 64 bits into 7 bits while preserving the value modulo 65 (65 = 2^{6} + 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 7bit number. 
Modulo 2^{n} +1 adder 
We now can use an adder modulo 2^{n} + 1, if only to replace the final carrypropagate addition of the above reduction. 
Multiplier modulo 2^{n} + 1 
A number modulo 2^{n1} + 1 fits in n bits or the sum of two numbers with n–1 bits each. The generation of the n^{2} partial products modulo 2^{n1} + 1 adds a bias equal to 2^{n} + 2^{n1}– n – 2. The partial product reduction compensates for the bias . 
Partial products reduction modulo 2^{n} + 1 
The applet reduces (n1)×(n+1) +1 bits into two numbers n–1 bits each modulo 2^{n1}+ 1. These two output numbers should be added with the aforementioned adder modulo circuit. This reduction adds another bias equal to n (number of feedback). The compensation of the two biases modulo 2^{n1} + 1 consists merely in adding 5 during the reduction. 
Conversion from "RNS" into mixedradix system "MRS" 
The "Mixed Radix System" is a positional number system with weights (1) (m_{1}) (m_{1}m_{2})
(m_{1}m_{2}m_{3}) (m_{1}m_{2}m_{3}.....m_{n1 }) . In this
system X is written ( z_{1}½ z_{2}½
z_{3}½....½ z_{n
})_{MRS} with 0 £ z_{i} < m_{i}.
Note that digit set have the same range as RNS digits, but digits themselves are different. The value of X = z_{1 }+ m_{1 }×_{ }(z_{2 }+ m_{2 }×_{ }(z_{3 }+ m_{3 }×_{ }( ..... ))). 
Operators library 
A very comprehensive library for modular arithmetic operators has been developed in "A VHDL Library for Integer and Modular Arithmetic" 