K-CLUSTER RESIDUE NUMBER SYSTEM USING LOOK-UP TABLES WITH REDUCED DATA CAPACITY FOR ADDITION, SUBTRACTION, AND MULTIPLICATION OPERATIONS

Abstract

A k-cluster residue number system has a processor and a memory. The processor is used to generate an addition and subtraction look-up table and a multiplication look-up table based on periodic behaviors of the modulo to compress the sizes of the addition and subtraction look-up table and the multiplication look-up table. The addition and subtraction look-up table has 2m.sub.i cells for recording values from zero to (m.sub.i?1) in an ascending order twice, wherein m.sub.i is a coprime integer of a modular set of the k-cluster residue number system. The multiplication look-up table has S cells, where

[00001]$S=\left(\frac{m_i^2-1}{4}\right).$

Claims

1. A method for performing addition and subtraction operations in a k-cluster residue number system, the method comprising: generating an addition and subtraction look-up table comprising 2m.sub.i cells for recording values from zero to (m.sub.i?1) in an ascending order twice, wherein m.sub.i is a coprime integer of a modular set of the k-cluster residue number system; storing the addition and subtraction look-up table in a memory of the k-cluster residue number system; retrieving a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod m.sub.i)+(B mod m.sub.i)); and retrieving a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+(mi?ry)=rx+ry, rx is equal to (X mod m.sub.i), ry is equal to (Y mod m.sub.i), and ry is equal to (m.sub.i?(Y mod m.sub.i)).

2. The method of claim 1 further comprising: generating a multiplication look-up table for the coprime integer m.sub.i, wherein the coprime integer m.sub.i is not 2, and the multiplication look-up table is composed of S cells, where $S=\left(\frac{m_i^2-1}{4}\right);$ and storing the multiplication look-up table in the memory.

3. The method of claim 2 further comprising: performing a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table, comprising: determining whether a complement of the multiplicand is greater than or equal to the multiplicator; if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps: selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry; if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps: selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry; if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; and retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry.

4. A method for performing multiplication operations in a k-cluster residue number system, the method comprising: generating a multiplication look-up table for a coprime integer m.sub.i of a modular set of the k-cluster residue number system, wherein the coprime integer m.sub.i is not 2, the multiplication look-up table is composed of S cells, $S=\left(\frac{m_i^2-1}{4}\right);$ and storing the multiplication look-up table in a memory of the k-cluster residue number system; and performing a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table, comprising: determining whether a complement of the multiplicand is greater than or equal to the multiplicator; if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps: selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry; if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps: selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry; if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; and retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry.

5. The method of claim 4 further comprises: generating an addition and subtraction look-up table comprising 2m.sub.i cells for recording values from zero to (m.sub.i?1) in an ascending order twice; and storing the addition and subtraction look-up table in the memory of the k-cluster residue number system.

6. The method of claim 5 further comprises: retrieving a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod m.sub.i)+(B mod m.sub.i)).

7. The method of claim 5 further comprises: retrieving a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+(mi?ry)=(rx+ry), rx is equal to (X mod m.sub.i), ry is equal to (Y mod m.sub.i), and ry is equal to (m.sub.i?(Y mod m.sub.i)).

8. A k-cluster residue number system comprising: a processor configured to: generate an addition and subtraction look-up table comprising 2m.sub.i cells for recording values from zero to (m.sub.i?1) in an ascending order twice, wherein m.sub.i is a coprime integer of a modular set of the k-cluster residue number system; retrieve a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod m.sub.i)+(B mod m.sub.i)); and retrieve a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+(mi?ry)=(rx+ry), rx is equal to (X mod m.sub.i), ry is equal to (Y mod m.sub.i), and ry is equal to (m.sub.i?(Y mod m.sub.i)); and a memory coupled to the processor and configured to store the addition and subtraction look-up table.

9. The k-cluster residue number system of claim 8, wherein the processor is further configured to: generate a multiplication look-up table for the coprime integer m.sub.i, wherein the coprime integer m.sub.i is not 2, and the multiplication look-up table is composed of S cells, where $S=\left(\frac{m_i^2-1}{4}\right);$ and store the multiplication look-up table in the memory.

10. The k-cluster residue number system of claim 9, wherein the processor is further configured to: perform a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table by performing the following steps: determining whether a complement of the multiplicand is greater than or equal to the multiplicator; if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps: selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry; if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps: selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry; if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; and retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry.

11. A k-cluster residue number system, comprising: a processor configured to: generate a multiplication look-up table for a coprime integer m.sub.i of a modular set of the k-cluster residue number system, wherein the coprime integer m.sub.i is not 2, and the multiplication look-up table is composed of S cells, $S=\left(\frac{m_i^2-1}{4}\right);$ and perform a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table by performing the following steps: determining whether a complement of the multiplicand is greater than or equal to the multiplicator; if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps: selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry; if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps: selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry; if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry; and if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry; and retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry; and a memory coupled to the processor and configured to store the multiplication look-up table.

12. The k-cluster residue number system of claim 11, wherein the processor is further configured to: generate an addition and subtraction look-up table comprising 2m.sub.i cells for recording values from zero to (m.sub.i?1) in an ascending order twice; and store the addition and subtraction look-up table in the memory of the k-cluster residue number system.

13. The k-cluster residue number system of claim 12, wherein the processor is further configured to: retrieve a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod m.sub.i)+(B mod m.sub.i)).

14. The k-cluster residue number system of claim 12, wherein the processor is further configured to: retrieve a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+(mi?ry)=(rx+ry), rx is equal to (X mod m.sub.i), ry is equal to (Y mod m.sub.i), and ry is equal to (m.sub.i?(Y mod m.sub.i)).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] FIG. 1 shows a k-cluster residue number system (k-RNS) according to an embodiment of the present invention.

[0022] FIG. 2 to FIG. 4 are illustrated to explain how the processor in FIG. 1 generates the addition and subtraction look-up table.

[0023] FIG. 5 shows a multiplication look-up table according to an embodiment of the present invention.

[0024] FIG. 6 is a flow chart when the processor in FIG. 1 retrieves data from the multiplication look-up table in FIG. 5.

[0025] FIG. 7 and FIG. 8 show a temporary multiplication look-up table and are used to explain how the processor in FIG. 1 generates the multiplication look-up table stored in the memory.

[0026] FIG. 9 shows the multiplication look-up table in FIG. 1 when the modular set of the k-RNS includes 7.

[0027] FIG. 10 is a flow chart when the processor in FIG. 1 retrieves data from one of the multiplication look-up tables.

DETAILED DESCRIPTION

[0028] To represent an n-bit integer and its negative using a k-cluster residue number system (k-RNS), it first defines a modular set of P coprime integers as (m.sub.0, m.sub.1, . . . , m.sub.p) where a dynamic range is generated according to the product of the modular set (m.sub.0, m.sub.1, . . . , m.sub.p). For example, when a modular set of 3 coprime integers is chosen to be (2.sup.n/2?1, 2, 2.sup.n/2+1) , the dynamic range is set to [?(2.sup.n?1), (2.sup.n?2)]. The modular set is not limited to 3 coprime integers.

[0029] FIG. 1 shows a k-cluster residue number system (k-RNS) 2 according to an embodiment of the present invention. The k-RNS 2 may comprise a processor 4, and a memory 6 coupled to the processor 4. The processor 4 is used to generate an addition and subtraction look-up table 10 and a multiplication look-up table 12. Memory 6 is used to store the addition and subtraction look-up table 10 and the multiplication look-up table 12.

[0030] Processor 4 uses the addition and subtraction look-up table 10 to perform addition operations and subtraction operations. FIG. 2 to FIG. 4 are illustrated to explain how processor 4 generates the addition and subtraction look-up table 10. According to the division algorithm, the following equation (4) in an integral domain could be transformed into the following equation (5) in a remainder domain:

Z=X+Y (4)

rz=rx+ry (5) [0031] where: [0032] X, Y, and Z are three integers; [0033] rx is equal to (X mod m.sub.i); [0034] ry is equal to (Y mod m.sub.i); [0035] rz is equal to (Z mod m.sub.i); and [0036] m.sub.i is selected from the modular set of the k-cluster residue number system 2.

[0037] In the embodiment, one modulus of the modular set selected by processor 4 is 7. However, the present invention is not limited thereto. The selected modulus could be other coprime integers of the modular set. The addition and subtraction look-up table 10 is composed of 14 (i.e., 2?7) cells 11 for recording values from zero to 6 in an ascending order twice. The addition and subtraction look-up table 10 is a one-dimensional linear array, which is simplified from a traditional two-dimensional addition look-up table A7 for addition operations based on modulus 7. The traditional addition look-up table A7 comprises 49 (i.e., 7?7) cells, more than fourteen cells 11 of the addition and subtraction look-up table 10. Each of the cells 11 is used to store a residue when an addition operation on two remainders rx and ry or two integers X and Y is performed, where rx=(X mod 7) and ry=(Y mod 7). The addition look-up table A7 is transformed to the addition and subtraction look-up table 10 based on the periodic behaviors of the modulo. As shown in FIG. 2, the sum stored in each cell of the addition look-up table A7 differs by one from the adjacent one. Therefore, the addition look-up table A7 could be simplified and transformed into the addition and subtraction look-up table 10. The remainder rx (i.e., the augend) may be used as the table entry, and the remainder ry (i.e., the addend) maybe used as the table index in ascending order to retrieve the result. In the embodiment, a start position Ps would be set to be equal to the augend rx, and the start position Ps would be shifted according to the addend ry. In detail, when the addition operation on two integers X and Y is performed, a value recorded in cell 11 at position Q of the addition and subtraction look-up table 10 is retrieved as the result of the addition operation, where Q=((X mod m.sub.i)+(Y mod m.sub.i)), and m.sub.i is the modulus. Since m.sub.i=7, (X mod m.sub.i)=(X mod 7)=rx, and (Y mod m.sub.i)=(Y mod 7)=ry, Q=(rx+ry). For example, when rx=4 and ry=5, the start position Ps is set to 4, and the Ps is shifted to 5, the value recorded in cell 11 at position 9 (i.e., 4?5=9) would be retrieved as the result of (rx+ry).

[0038] Similarly, according to the subtraction algorithm, the following equation (6) in the integral domain could be transformed into the following equation (7) in the remainder domain:

Z=X?Y (6)

rz=rx?ry (7)

[0039] Therefore, the addition and subtraction look-up table 10 could be used not only for addition operations but also for subtraction operations since the addition and subtraction look-up table 10 could be obtained by simplifying a traditional subtraction look-up table S7. The traditional subtraction look-up table S7 also comprises 49 (i.e., 7?7) cells, more than fourteen cells 11 of the addition and subtraction look-up table 10. Each of the cells 11 is used to store a residue when the remainder rx is subtracted by the remainder ry. The subtraction look-up table S7 is transformed to the addition and subtraction look-up table 10 based on periodic behaviors of the modulo. As shown in FIG. 3, the value stored in each cell 11 of the subtraction look-up table S7 differs by one from the adjacent one. Therefore, the subtraction look-up table S7 could be simplified and transformed into the addition and subtraction look-up table 10. A sum of the remainder rx (i.e., the minuend) and the modulus mi may be used as the table entry, and the remainder ry (i.e., the subtrahend) may be used as the table index in descending order to retrieve the result. In the embodiment, a start position Ps would be set to be equal to the sum of the minuend rx and the modulus m.sub.i, and the start position Ps would be shifted according to the subtrahend ry. In detail, when the addition operation on two integers X and Y is performed, a value recorded in cell 11 at position R of the addition and subtraction look-up table 10 is retrieved as the result of the subtraction operation, where R=(m.sub.i+(X mod m.sub.i)?(Y mod m.sub.i)). Since m.sub.i=7, (X mod m.sub.i)=(X mod 7)=rx, and (Y mod m.sub.i)=(Y mod 7)=ry, R=(m.sub.i+rx?ry). For example, when we subtract 5 with 4, rx=5 and ry=4, the table entry becomes (5+7)=12, where 7 is equal to mi, then, it shifts to the left by 4, the value recorded in the cell 11 at position 8 is defined as 1, it matches the result of (rx?ry)=1.

[0040] In another embodiment of the present invention, when processor 4 subtracts the integer X by the integer Y, processor 4 retrieves the value from the addition and subtraction look-up table 10 according to the complement ry of the remainder ry and the remainder rx (i.e., the minuend). Referring to FIG. 4, in the embodiment, the remainder rx (i.e., the minuend) may be used as the table entry, and the complement ry may be used as the index in ascending order to retrieve the result. In detail, when the processor 4 subtracts the integer X by the integer Y, the processor 4 retrieves a value recorded in a cell 11 at position R of the addition and subtraction look-up table 10, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+(mi?ry)=rx?ry and ry is the complement of the remainder ry (i.e., ry=m.sub.i?ry). The complement ry may be obtained according to a complement table. For example, when m.sub.i=7, a complement table can be illustrated as follows:

TABLE-US-00001 ry 0 1 2 3 4 5 6 ry 0 6 5 4 3 2 1

[0041] Since R=(rx+ry), the start position Ps would be set to be rx of the addition and subtraction look-up table 10, then it is shifted according to the complement ry. For example, when we subtract 5 with 4, rx=5 and ry=4, the table entry becomes=5, the complement of ry=4 is ry=3, it shifts to the right by 3, the value recorded in cell 11 at position 8 is defined as 1, it matches the result of (rx?ry)=1.

[0042] Therefore, the two-dimensional addition look-up table A7 and the two-dimensional subtraction look-up table S7 could be simplified and transformed into the addition and subtraction look-up table 10, which is a one-dimensional linear array. The addition and subtraction look-up table 10 is used by processor 4 when processor 4 performs an addition operation or a subtraction operation when the modulus m.sub.i=7. Since the modulus m.sub.i may be an integer other than 7, processor 4 could generate corresponding addition and subtraction look-up tables for other coprime integers of the modular set.

[0043] In detail, if the k-RNS 2 uses P coprime integers to define its modular set as (m.sub.1, . . . , 2, . . . , m.sub.p), the processor 4 generates a corresponding addition and subtraction look-up table for each coprime integer not equal to 2. If the coprime integer is m.sub.i, its corresponding addition and subtraction look-up table is composed of 2m.sub.i cells 11 for recording values from zero to (m.sub.i?1) in an ascending order twice. When processor 4 performs an addition operation on two integers X and Y, processor 4 retrieves a value recorded in cell 11 at position Q of the addition and subtraction look-up table 10, where Q=((X mod m.sub.i)+(Y mod m.sub.i))=(rx+ry). When processor 4 subtracts the integer X by the integer Y, processor 4 retrieves a value recorded in cell 11 at position R of the addition and subtraction look-up table 10, where R=(X mod mi)?(Y mod mi)=(X mod mi)+(mi?(Y mod mi))=rx+ry, and ry is the complement of the remainder ry (i.e., ry=m.sub.i?ry). According to the subtraction algorithm, the following equation (8) in the integral domain could be transformed into the following equation (9) in the remainder domain:

Z=X?Y (8)

rz=(rx?ry) (9) [0044] where: [0045] X, Y, and Z are three integers; [0046] rx is equal to (X mod m.sub.i); [0047] ry is equal to (Y mod m.sub.i); [0048] rz is equal to (Z mod m.sub.i); and [0049] m.sub.i is selected from the modular set of the k-cluster residue number system 2.

[0050] FIG. 5 shows a multiplication look-up table 60 according to an embodiment of the present invention. A product of two integers X and Y would be zero if one of two integers X and Y is zero, so all cells whose value is equal to zero in a multiplication look-up table could be eliminated. Accordingly, the data amount of the temporary multiplication look-up table 60 could be presented as the following equation (10):

[00006]$\begin{array}{cc}Mem2=\underset{i=0}{\overset{n}{.Math.}}{\left(m_i-1\right)}^2?b_i& \left(10\right)\end{array}$ [0051] where: [0052] Mem2 is the data amount of the temporary multiplication look-up table 60; [0053] m.sub.i is the i.sup.th modulus; and [0054] b.sub.i is the number of bits of the i.sup.th modulus.

[0055] According to equations (2) and (10), the lookup table size is reduced from

[00007]$\underset{i=0}{\overset{n}{.Math.}}{m}_i^2$

to

[00008]$\underset{i=0}{\overset{n}{.Math.}}{\left(m_i-1\right)}^2$

as compared with the prior art. Moreover, according to the multiplication commutative rule, the order of the multiplicand and multiplicator can be exchanged. Therefore, the products of the temporary multiplication look-up table 60 could be mirrored along a Top-Left and Bottom-Right (TL/BR) diagonal line 62, as shown in FIG. 5.

[0056] FIG. 6 is a flow chart when processor 4 in FIG. 1 retrieves data from the multiplication look-up table 60 in FIG. 5. Processor 4 first receives rx (Step S602) and ry (Step S604), then compares rx with ry (Step S606). If rx is greater than or equal to ry, processor 4 keeps rx and ry without changes (Step S608), so that rx is selected as a column entry and ry is selected as a row entry to access the multiplication look-up table 60; otherwise, the processor 4 interchanges rx and ry positions for memory location access (Steps S610 and S612), so that ry is selected as a column entry and rx is selected as a row entry to access the multiplication look-up table 60. In Step S608, rx is selected as a column entry and ry is selected as a row entry. In Step S612, ry is selected as a column entry and rx is selected as a row entry to access the multiplication look-up table 60. In Step S614, processor 4 retrieves data from the multiplication look-up table 60 according to the column entry and row entry. This approach can reduce the memory size by half.

[0057] FIG. 7 and FIG. 8 show a temporary multiplication look-up table 60 and are used to explain how the processor in FIG. 1 generates one of the multiplication look-up tables 12 stored in memory 6. In the embodiment, the k-RNS 2 offers additional mirror property based on periodic behaviors of the modulo, the products of the temporary multiplication look-up table 60 could be mirrored along with a Top-Right and Bottom-Left (TR/BL) diagonal line 64, as shown in FIG. 7. Therefore, the temporary multiplication look-up table 60 can be partitioned into four identical regions 81, 82, 83 and 84, as shown in FIG. 8, to reduce the table size. Accordingly, the lookup table size for multiplication operations may be further reduced from

[00009]$\underset{i=0}{\overset{n}{.Math.}}{\left(m_i-1\right)}^2$

to

[00010]$\underset{i=0}{\overset{n}{.Math.}}\left(m_i^2-1\right)/4.$

For example, the multiplication look-up table 12 has twelve cells 11 while the temporary multiplication look-up table 60 has thirty-six cells 11. Therefore, the lookup table size for multiplication operations is further reduced. Due to the mirror property and the periodic behaviors of the modulo, the four identical regions 81, 82, 83, and 84 could be simplified as a multiplication look-up table 12, as shown in FIG. 9. The multiplication look-up table 12 is corresponding to modulus 7 (i.e., m.sub.i=7). Processor 4 may generate a multiplication look-up table 12 for each coprime integer of the modular set, and a multiplication look-up table for the coprime integer m.sub.i is composed of S cells 11, where

[00011]$S=\left(\frac{m_i^2-1}{4}\right).$

[0058] Accordingly, the data amount of the multiplication look-up table 12 could be presented as the following equation (11):

[00012]$\begin{array}{cc}Mem3=\underset{i=0}{\overset{n}{.Math.}}\left(\frac{m_i^2-1}{4}\right)?b_i& \left(11\right)\end{array}$ [0059] where: [0060] Mem3 is the data amount of the multiplication look-up table 12; [0061] m.sub.i is the i.sup.th modulus; and [0062] b.sub.i is the number of bits of the i.sup.th modulus.

[0063] When processor 4 performs a multiplication operation on the two integers X and Y, processor 4 would perform the procedure shown in FIG. 10. To access the correct stored product location, processor 4 selects the multiplicand (rx) as the lookup table column entry and the multiplicator (ry) as the row entry, then modifies or keeps the two entries to access the product stored in a different region. In detail, when processor 4 performs a multiplication operation on a multiplicand rx and a multiplicator ry using the multiplication look-up table 12, the multiplication operation may comprise the following steps:

[0064] Step S902: determine whether a complement rx of the multiplicand rx is greater than or equal to the multiplicator ry; if it is determined that the complement rx of the multiplicand rx is greater than or equal to the multiplicator ry, go to Step S904; otherwise, go to Step S914;

[0065] Step S904: select the multiplicand rx as the column entry and the multiplicator ry as the row entry;

[0066] Step S906: determine whether the column entry (rx) is greater than or equal to the row entry (ry); if it is determined that the column entry (rx) is greater than or equal to the row entry (ry), go to Step 908; otherwise, go to Step S910;

[0067] Step 908: keep the column entry and the row entry; go to Step 924

[0068] Step 910: interchange the column entry and the row entry;

[0069] Step 912: ry is selected as the column entry and rx is selected as the row entry; go to Step S924

[0070] Step S914: select the complement rx of rx as the column entry and the complement ry of the multiplicator ry as the row entry;

[0071] Step S916: determine whether the column entry (rx) is greater than or equal to the row entry (ry); if it is determined that the column entry (rx) is greater than or equal to the row entry (ry), go to Step S918; otherwise go to step S920;

[0072] Step S918: keep the column entry (rx) and the row entry (ry); Go to Step S924

[0073] Step S920: interchange the column entry (rx) and row entry (ry);

[0074] Step S922: the complement ry of ry is selected as the column entry and complement rx of rx is selected as the row entry; go to Step 924

[0075] Step 924: Retrieve a value from the multiplication look-up table 12 as a product of the multiplicand and the multiplicator according to the column entry and the row entry.

[0076] Briefly, processor 4 changes the column entry from rx to its RNS complement rx, where rx=(m.sub.i?rx), then processor 4 compares rx with ry (step S902). If rx is less than ry, then both the row and column entries are changed into their residue complement (step S114, where rx=(m.sub.i?rx) and ry=(m.sub.i?ry)), otherwise keeping rx and ry without change (step S904). After that, processor 4 compares the row (rx) and column (ry) entries. If rx is less than ry, then rx and ry are interchanged (rx?ry) for table access.

[0077] For example, when m.sub.i=7, X=10, and Y=19, rx=3, ry=5, rx=7?3=4, ry=7?5=2 According to the above approach, the column entry is rx=4, and the row entry is ry=2. Therefore, when processor 4 performs a multiplication operation on X and Y, processor 4 would retrieve the value recorded in cell 11 at the 4.sup.th column and 2.sup.nd row of the multiplication look-up table 12 as the product of the modulo multiplication. The product of X=10 and Y=19 is 190, where the residue |190|.sub.7=1. It is consistent with the value: 1 stored in 4.sup.th column and 2.sup.rd row. In another example, when m.sub.i=7, X=11, and Y=15, rx=4, ry=1, rx=7?4=3, ry=7?1=6, the column entry is rx=4, and the row entry is ry=1. Therefore, when processor 4 performs a multiplication operation on X and Y (i.e., 11?15), where the residue |165|.sub.7=4, processor 4 would retrieve the value: 4 recorded in cell 11 at the 4.sup.th column and 1.sup.st row of the multiplication look-up table 12 as the product of the multiplication.

[0078] In the k-cluster residue number system 2, since the addition and subtraction look-up table 10 and the multiplication look-up table 12 have compressed size, the required size of the memory 6 for storing look-up tables for addition, subtraction, and multiplication operations could be reduced.

[0079] Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.