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 "end-around-carry" 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 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 * ( ..... ))).