R N S       Residue Number System    resources    preliminary /
under construction

Modular Multiplication

One of the advantages of the use of moduli of small dynamic range which are prime numbers, is that we can transform modular multiplication into a modular addition by the isomorphism technique [2].

The isomorphic transformation is based on the concept of indices that are similar to logarithms, and primitive roots r which are similar to logarithm bases. It is possible to demonstrate that if the number m is prime there exists a number of primitive radices (the number of the primitive radices can be computed by using the Euler's function) that share the following property: every element of the field F(m) = {0, 1, ..., m-1 excluding the zero element can be generated by using the following equation
F(m) = < rk >m
(7)
where k is an integer number. In Figure 4 the generation of the elements for F(11) is shown. In this case the four primitive radices {2, 6, 7, 8} can be utilized.

Figure 4: The isomorphism table for m = 11.

The product of two elements a1 and a2 belonging to the field is implemented by

  1. Forward transformation of a1 and a2 in the corresponding indices
  2. Addition modulo m-1 of the two indices
  3. Reverse conversion of the result of the addition to obtain the final result of the modular product

If the modulus is small (its representation is six or seven bits), the forward and reverse transformations can be implemented by look-up table of reasonable size which are then synthesized into multi-level combinational logic.

Therefore, the product of a1 and a2 modulo m can be obtained as:
< a1 + a2 >m = < qw >m
where
w = < w1 + w2 >m- 1      with   a1 = < qw1 >m   and   a2 = < qw2 >m
In order to implement the modular multiplication the following operations are performed:

  1. Two Direct Isomorphic Transformations (DIT) to obtain w1 and w2;
  2. One modulo m-1 addition < w1 + w2 >m- 1 ;
  3. One Inverse Isomorphic Transformations (IIT) to obtain the product.

The architecture of the isomorphic multiplier is shown in Figure 5.

Figure 5: Structure of isomorphic multiplication.

An alternative for isomorphic multiplication was proposed in [5]. Because isomorphic multipliers use modular adders in combination with tables, one of the adders in Figure 3 is eliminated and the modulus operation is incorporated in the IIT table. Moreover, the addition of the constant -mI is incorporated in one of DIT tables (called DIT*), as well. The resulting scheme, shown in Figure 6, is faster and consumes less power, as detailed in [5].

Figure 6: Structure of modified isomorphic multiplier.

Resources

Multiplication by Isomorphism Applet

[Home]    < Previous    Next >