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 2n1

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 2n1

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 n1 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 n1 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) ( ) . 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"