# Revisiting Sum of Residues Modular Multiplication

Authors: Yinan Kong; Braden Phillips
Journal: Journal of Electrical and Computer Engineering
 (2010)

---

## Abstract

In the 1980s, when the introduction of public key
cryptography spurred interest in modular multiplication, many
implementations performed modular multiplication using a sum
of residues. As the field matured, sum of residues modular
multiplication lost favor to the extent that all recent surveys
have either overlooked it  or incorporated it within a larger class
of reduction algorithms.
In this paper, we present a new taxonomy of modular multiplication
algorithms. We include sum of residues as one of four
classes  and argue why it should be considered different to the
other, now more common, algorithms. We then apply techniques
developed for other algorithms to reinvigorate sum of residues
modular multiplication. We compare FPGA implementations of
modular multiplication up to 24 bits wide. The sum of residues
multipliers demonstrate reduced latency at nearly 50% compared
to Montgomery architectures at the cost of nearly doubled circuit
area. The new multipliers are useful for systems based on the
Residue Number System (RNS).


---

## Body

## 1. Introduction

Modular multiplication is important for many applications including cryptography and image processing. Many different modular multiplication algorithms have been published [1–5] and have been deployed for public-key cryptography or digital signal processing. In this paper, we reinvigorate the sum of residues class of modular multipliers by describing a new modular multiplication algorithm and implementation.Section3 surveys the literature of modular multiplication to arrive at 4 classes of algorithm: sum of residues, classical, Barrett and Montgomery. The goal of this section is not a comprehensive survey all publications, but to support the claim that sum of residues is a distinct class that has been largely ignored. In Section 4, we apply optimizations, originally proposed for other classes of reduction, to breathe new life into sum of residues modular multiplication. Section 5 evaluates the reinvigorated sum of residues approach by comparing it with  Montgomery multiplication on an FPGA.


## 2. Motivation: The Residue Number System

Our interest in modular multiplication at word length up to around 24-bits stems from its application to systems built using the Residue Number System (RNS). By representing integers in independent short-word length channels, residue number systems offer advantages for digital signal processing [6–8] and long word length arithmetic, especially for crypto-operations [9, 10].A residue number system [11] is characterized by a set of N coprime moduli {m1,m2,…,mN}. In the RNS, a number X is uniquely represented in N channels: X={x1,x2,…,xN}, where xi is the residue of X with respect to mi, that is, xi=〈X〉mi=Xmodmi.IfX, Y, and Z have RNS representations given by X={x1,x2,…,xN}, Y={y1,y2,…,yN}, and Z={z1,z2,…,zN}, then denoting * to represent the operations +, −, or ×, the RNS version of Z=X*Y satisfies (1)Z={〈x1*y1〉m1,〈x2*y2〉m2,…,〈xN*yN〉mN}.
Thus, addition, subtraction, and multiplication can be concurrently performed on the N residues within N parallel channels, and it is this high-speed parallel operation that makes the RNS attractive. The multipliers described in this paper are intended for the modular multiplications 〈xi×yi〉mi within RNS channels. These typically have a word length from 4 to 24 bits.


### 2.1. Contribution

This paper contributes to the literature of modular multiplication by(1)
identifying sum of residues as a separate class of modular reduction algorithm,(2)
presenting a new algorithm and implementation for sum of residues modular multiplication, and(3)
demonstrating that this approach can deliver performance benefits, particularly for channel-width modular multipliers for RNS systems on FPGA.


### 2.2. Notation

We consider the modular multiplicationC=A×BmodM, where A, B, and M are n-digit integers of the form X=∑i=0n-1xiri. The radix r is typically a positive power of 2.Note that it is common for modular multiplication algorithms to produce a resultC>M such that a few subtractions of M are required to fully reduce the result. The usual approach is to design the algorithm so C can be fed back to the input without overflow, even if C is not fully reduced.


## 2.1. Contribution

This paper contributes to the literature of modular multiplication by(1)
identifying sum of residues as a separate class of modular reduction algorithm,(2)
presenting a new algorithm and implementation for sum of residues modular multiplication, and(3)
demonstrating that this approach can deliver performance benefits, particularly for channel-width modular multipliers for RNS systems on FPGA.


## 2.2. Notation

We consider the modular multiplicationC=A×BmodM, where A, B, and M are n-digit integers of the form X=∑i=0n-1xiri. The radix r is typically a positive power of 2.Note that it is common for modular multiplication algorithms to produce a resultC>M such that a few subtractions of M are required to fully reduce the result. The usual approach is to design the algorithm so C can be fed back to the input without overflow, even if C is not fully reduced.


## 3. Classes of Modular Multiplication

Some early modular multipliers [4, 12–15] proceed by accumulating residues modulo M. Equation (2) is a typical starting point. The residues, typified by (BrimodM) in (2), may be precomputed and retrieved from a table (e.g., [12]) or evaluated recursively during the modular multiplication (e.g., [13]). A typical algorithm will be shown in the next section, from which point the sum of residues algorithm will be analyzed and improved (2)C=∑i=0n-1ai(Brimod⁡M).Instead of accumulating residues moduloM, reduction can be performed by subtracting multiples of M. Papers that take this approach include [5, 16–19]. Algorithm 1 is typical. Reduction in this way can be understood as a division in which the quotient is discarded and the remainder retained. Development of modular multipliers along this line has, therefore, closely followed the development of division, especially SRT division (as originally in [20]).Algorithm 1:A Typical Example of Classical Modular Multiplication.
Ensure: C≡A×BmodMC=0fori=n-1 downto 0doC=rC+aiB{Partialproductaccumulation}qi=QDS(C,M){Quotientdigitselection}C=C-qiM{Reductionstep}end forThe Quotient Digit Selection function (QDS) has received a great deal of attention to: permit quotient digits (qi) to be trivially estimated from only the most significant bits of the partial result C, allow the partial result to be stored in a redundant form,  and move the QDS function from the critical path (e.g., [17, 18]).The relationship between division and modular multiplication is made explicit in(3)A×Bmod⁡M=(A×B)-⌊A×BM⌋×M.
This equation suggests an alternative mechanism: one may perform the division ⌊(A×B)/M⌋ by multiplying by M-1. Papers that follow this line include [1, 21, 22]. Note that M-1 is a real number so that correct evaluation of (3) using fixed-point arithmetic requires careful design of the representation. A typical example is the improved Barrett algorithm (named after Barrett's reduction in [1]) described in [22] and shown in Algorithm 2.Algorithm 2:Improved Barrett modular multiplication.
Require:α, β{Pre-definedparameters}Require:K=⌊2n+α/M⌋{Aprecomputedconstant}Ensure:C≡A×BmodMC=A×BC1=⌊C/2n+β⌋{Rightshiftbyn+β}C2=C1×KQ=⌊C/2α-β⌋C=C-Q×MMost recently, modular multipliers based on Montgomery's reduction algorithm [2] have been popular [3, 23, 24]. A typical form is shown in Algorithm 3. Note that the quotient digit selection step examines only the least significant digit of the partial result C. Also, note that Montgomery's method does not produce a fully reduced residue C=A×BmodM directly, but rather the Montgomery residue C×R-1modM. Computation can proceed with Montgomery residues as an internal representation. An extra modular multiplication is required to convert the final result to a fully reduced residue.Algorithm 3:Montgomery modular multiplication.
Require:R=rnRequire:m0-1s.t.m0×m0-1≡1modrEnsure:C≡A×B×R-1modMC=0fori=0 to n-1doC=C+aiB{Partialproductaccumulation}qi=-c0×m0-1modM{Quotientdigitselection}C=(C+qiM)/r{Reductionstep}end forWe have, therefore, identified 4 different classes of modular multiplication algorithm according to the way in which they perform reduction.(1)
Sum of Residues:   reduction is achieved by accumulating residues modulo M.(2)
Classical:  multiples of the modulus qiM are subtracted according to a QDS function that examines the most significant digits of the partial result C.(3)
Barrett:  multiplication by M-1 is used to reduce modulo M.(4)
Montgomery:  multiples of the modulus qiM are accumulated according to a QDS function that examines the least significant digits of the partial result C.We note here that each of the 4 classes permits separated and interleaved implementations. In a separated implementation,A×B is evaluated before being reduced modulo M. The alternative is to interleave the multiplication and reduction steps. This has the benefit of keeping intermediate values to the approximate magnitude of M but does not take advantage of any preexisting nonmodular multiplier. In this paper, we are largely concerned with interleaved implementations.Surveys of modular reduction offer different classifications. References  [25–27] identify three classes: classical, Barrett, and Montgomery. References [22, 28] include the Barrett algorithms with other classical algorithms and therefore divide the field into only two classes: classical and Montgomery. None of these surveys cover sum of residues papers. Other publications, [4, 29, 30], have made note of the sum of residues technique but categorize it along with other classical algorithms.


## 4. Reinvigorating Sum of Residues

### 4.1. Tomlinson's Algorithm

We take the modular multiplier developed by Tomlinson in [4] as our starting point for further development. Tomlinson's algorithm is shown in Algorithm 4.Algorithm 4:Tomlinson's sum of residues modular multiplication.
Ensure:C≡A×BmodM, C<2n+1C=0q=0fori=n-1 downto 0doC=2C+aiBC=C+(q×2n+1modM){Theresidue(q×2n+1modM)isprecomputed.}q=⌊C/2n⌋{qistheupper2bitsofC}C=C-q×2n{Settheupper2bitsofCtozero}end forC=2C+(q×2n+1modM)At first sight, this may look like a classical algorithm as the quotient digitq is selected from the most significant bits of the partial result. The difference is that a classical algorithm then performs reduction by subtracting the multiple of the modulus qiM; Tomlinson's algorithm performs the reduction by setting the most significant bits to zero and accounting for this change by adding the precomputed residue (q×2n+1modM).An architecture for Tomlinson's algorithm is shown in Figure1. Note that the intermediate result C at iteration i is denoted C[i]. As the loop is from n-1 down to 0, C[i+1] denotes the value C in the previous iteration.Figure 1
An architecture for Tomlinson's interleaved modular multiplication algorithm.A Carry-Save Adder (CSA) is used to perform the three-term additionC[i]=2C[i+1]+aiB+(q×2n+1modM). To make sure 2C[i+1] is n bits long, the same as the other two addends, q is set to be the upper 3 bits instead of 2 bits of the current partial result.Note that the carry-save representation is a type of redundant representation that has been applied to other modular multiplication algorithms [15, 19, 31]. We will keep using this technique to enhance the sum of residues modular multiplier.Reference [15] gives an similar algorithm but sets q only two bits long. This means that the partial result C[i] may be n+1 bits long. To bound it within n bits, a subtracter is used to constantly subtract M until C[i] has only n bits. This redundant step greatly increases the latency of the algorithm. In the following sections, we describe new enhancements to improve the performance of this algorithm.


### 4.2. Eliminating the Carry-Propagate Adder

There two obvious demerits of the architecture in Figure1. Firstly, a Carry-Propagate Adder (CPA) is used to transform the redundant representation of C[i] to its nonredundant form. This is required because the upper 3 bits of C[i] have to be known to look up q×2n mod M before the next iteration. The CPA delay contributes significantly to the latency of the implementation. The second problem is that the lookup of q×2n mod M is on the critical path.Both of these problems can be solved by keeping the intermediate result in a  redundant carry-save form. The CPA of Figure1 is eliminated so that the calculation of the partial result becomes C1[i]+C2[i]=C1[i+1]+C2[i+1]+aiB+((q1+q2)×2nmodM), where C1[i] and C2[i] are the redundant representation of C[i] as sum and carry terms,  respectively. A modified architecture is shown in Figure 2. The CPA is replaced by a second CSA.Figure 2
Modified sum of residues modular multiplier architecture.The precomputed residue(q1+q2)×2nmodM, which must be retrieved from a lookup table (LUT), can be sent to the second CSA rather than the first. All three addends to the first CSA are available at the beginning of each iteration and the table lookup step can be performed in parallel with the first CSA.In Figure1, it can be seen that the carry output of the first CSA is n+1 bits wide. This cannot be input directly to the second CSA which is only n-bits wide. Thus, in Figure 2, the MSB of the (n+1)-bit carry is sent to the LUT circuit instead. The LUT retrieves two possible values of (q1+q2)×2n mod M corresponding to the case of either a 0 or 1 in the MSB of the carry output from the first CSA. An MUX selects the appropriate value of (q1+q2)×2n mod M once the MSB is available. Thus, although the LUT executes in parallel with the first CSA, an additional MUX appears on the critical path.


### 4.3. Further Enhancements

If the second CSA in Figure2 can be modified to accept an (n+1)-bit input, the MUX can be eliminated. The left of Figure 3 shows a conventional n-bit CSA. Note that the output sum is only n bits wide. To accept an (n+1)-bit input, we can just copy the MSB of the (n+1)-bit input to the MSB of output sum. This is illustrated in the right of Figure 3. This modified CSA accepts 1 (n+1)-bit input and 2 n-bit inputs and produces 2 (n+1)-bit outputs.Figure 3
n-bit carry-save adders.Figure4 shows the resulting modular multiplication architecture. The algorithm corresponding to this new architecture is given as Algorithm 5. The CPA has been eliminated from the iteration, and the residue lookup has been shifted from the critical path. Also, no subtraction is needed at the end of the algorithm to bound the output within n+1 bits. If C1[0] and C2[0] are simply summed using a CPA, the resulting output C could be n+2 bits, which needs some further subtraction to be reduced. Therefore, the same technique as in the loop is applied. Both C1[0] and C2[0] are set to n-1 bits and the n-bit residue corresponding to the 2 upper reset bits is retrieved from another LUT. The final sum yields an (n+1)-bit output C.Algorithm 5:New sum of residues modular multiplication.
Ensure:C≡A×BmodM, C<2n+1C1[n]=C2[n]=q1=q2=0fori=n-1 downto 0do{T1[i],T2[i]}=2C1[i+1]+2C2[i+1]+aiB{Carrysaveaddition}{C1[i],C2[i]}=T1[i]+T2[i]+((q1+q2)×2nmodM){Carrysaveaddition}{Theresidue((q1+q2)×2nmodM)isprecomputed}{q1,q2}={C1[i]≫(n-1),C2[i]≫(n-1)}{q1 and q2 are the upper 2 bits of C1[i] and C2[i] respectively.}{C1[i],C2[i]}={2C1[i] & (2n-1),2C2[i] & (2n-1)}{Settheupper2bitsofC1[i]andC2[i]tozero}end for{C1[0],C2[0]}={2C1[0],2C2[0]}{Rightshiftsotheyarebothn-1bits}C=C1[0]+C2[0]+((q1+q2)×2n-1modM)Figure 4
New sum of residues modular multiplier architecture.The LUTs have a 4-bit input and ann-bit output so that a (24×n)-bit ROM can be used. Moreover, note that the sum of (q1+q2) is at most 110, which occurs when (q1 and q2) are both 11. This implies that the possible sum of (q1+q2) is in the range from 000 to 110, which has 7 values only. Therefore, a ROM with a further reduced size of (7×n) bits can be used for (q1+q2)×2nmodM. For example, a 128-bit modular multiplier only needs a 1K-bit ROM, which is reasonable for a RNS channel modular multiplier.Figure5 shows  an example of the new algorithm for the case r=2, n=4, A=15=(1111)2, B=11=(1011)2, and M=9=(1001)2. It is noted that at the last step, a second LUT of the same size is needed. Also, because the output C from the 4-bit CPA is at most 5 bits long, the final subtraction might not be necessary if a n+1-bit C is acceptable, as the case in quite a few other algorithms. Even if a 4-bit C is required, only one subtraction will do.Figure 5
An example for the new algorithmn=4, A=(1111)2, B=(1011)2, and M=(1001)2.


### 4.4. Higher Radix

High radix is another popular technique that has been adopted by other algorithms [17, 24]. It also contributes to the new sum of residues algorithm. A radix-r version of the algorithm can be produced as in Figure 6. If r=2k, this version executes in n/k iterations; however,  a larger LUT and (n+k)-bit CSAs are required.Figure 6
New higher-radix sum of residues modular multiplier architecture.


## 4.1. Tomlinson's Algorithm

We take the modular multiplier developed by Tomlinson in [4] as our starting point for further development. Tomlinson's algorithm is shown in Algorithm 4.Algorithm 4:Tomlinson's sum of residues modular multiplication.
Ensure:C≡A×BmodM, C<2n+1C=0q=0fori=n-1 downto 0doC=2C+aiBC=C+(q×2n+1modM){Theresidue(q×2n+1modM)isprecomputed.}q=⌊C/2n⌋{qistheupper2bitsofC}C=C-q×2n{Settheupper2bitsofCtozero}end forC=2C+(q×2n+1modM)At first sight, this may look like a classical algorithm as the quotient digitq is selected from the most significant bits of the partial result. The difference is that a classical algorithm then performs reduction by subtracting the multiple of the modulus qiM; Tomlinson's algorithm performs the reduction by setting the most significant bits to zero and accounting for this change by adding the precomputed residue (q×2n+1modM).An architecture for Tomlinson's algorithm is shown in Figure1. Note that the intermediate result C at iteration i is denoted C[i]. As the loop is from n-1 down to 0, C[i+1] denotes the value C in the previous iteration.Figure 1
An architecture for Tomlinson's interleaved modular multiplication algorithm.A Carry-Save Adder (CSA) is used to perform the three-term additionC[i]=2C[i+1]+aiB+(q×2n+1modM). To make sure 2C[i+1] is n bits long, the same as the other two addends, q is set to be the upper 3 bits instead of 2 bits of the current partial result.Note that the carry-save representation is a type of redundant representation that has been applied to other modular multiplication algorithms [15, 19, 31]. We will keep using this technique to enhance the sum of residues modular multiplier.Reference [15] gives an similar algorithm but sets q only two bits long. This means that the partial result C[i] may be n+1 bits long. To bound it within n bits, a subtracter is used to constantly subtract M until C[i] has only n bits. This redundant step greatly increases the latency of the algorithm. In the following sections, we describe new enhancements to improve the performance of this algorithm.


## 4.2. Eliminating the Carry-Propagate Adder

There two obvious demerits of the architecture in Figure1. Firstly, a Carry-Propagate Adder (CPA) is used to transform the redundant representation of C[i] to its nonredundant form. This is required because the upper 3 bits of C[i] have to be known to look up q×2n mod M before the next iteration. The CPA delay contributes significantly to the latency of the implementation. The second problem is that the lookup of q×2n mod M is on the critical path.Both of these problems can be solved by keeping the intermediate result in a  redundant carry-save form. The CPA of Figure1 is eliminated so that the calculation of the partial result becomes C1[i]+C2[i]=C1[i+1]+C2[i+1]+aiB+((q1+q2)×2nmodM), where C1[i] and C2[i] are the redundant representation of C[i] as sum and carry terms,  respectively. A modified architecture is shown in Figure 2. The CPA is replaced by a second CSA.Figure 2
Modified sum of residues modular multiplier architecture.The precomputed residue(q1+q2)×2nmodM, which must be retrieved from a lookup table (LUT), can be sent to the second CSA rather than the first. All three addends to the first CSA are available at the beginning of each iteration and the table lookup step can be performed in parallel with the first CSA.In Figure1, it can be seen that the carry output of the first CSA is n+1 bits wide. This cannot be input directly to the second CSA which is only n-bits wide. Thus, in Figure 2, the MSB of the (n+1)-bit carry is sent to the LUT circuit instead. The LUT retrieves two possible values of (q1+q2)×2n mod M corresponding to the case of either a 0 or 1 in the MSB of the carry output from the first CSA. An MUX selects the appropriate value of (q1+q2)×2n mod M once the MSB is available. Thus, although the LUT executes in parallel with the first CSA, an additional MUX appears on the critical path.


## 4.3. Further Enhancements

If the second CSA in Figure2 can be modified to accept an (n+1)-bit input, the MUX can be eliminated. The left of Figure 3 shows a conventional n-bit CSA. Note that the output sum is only n bits wide. To accept an (n+1)-bit input, we can just copy the MSB of the (n+1)-bit input to the MSB of output sum. This is illustrated in the right of Figure 3. This modified CSA accepts 1 (n+1)-bit input and 2 n-bit inputs and produces 2 (n+1)-bit outputs.Figure 3
n-bit carry-save adders.Figure4 shows the resulting modular multiplication architecture. The algorithm corresponding to this new architecture is given as Algorithm 5. The CPA has been eliminated from the iteration, and the residue lookup has been shifted from the critical path. Also, no subtraction is needed at the end of the algorithm to bound the output within n+1 bits. If C1[0] and C2[0] are simply summed using a CPA, the resulting output C could be n+2 bits, which needs some further subtraction to be reduced. Therefore, the same technique as in the loop is applied. Both C1[0] and C2[0] are set to n-1 bits and the n-bit residue corresponding to the 2 upper reset bits is retrieved from another LUT. The final sum yields an (n+1)-bit output C.Algorithm 5:New sum of residues modular multiplication.
Ensure:C≡A×BmodM, C<2n+1C1[n]=C2[n]=q1=q2=0fori=n-1 downto 0do{T1[i],T2[i]}=2C1[i+1]+2C2[i+1]+aiB{Carrysaveaddition}{C1[i],C2[i]}=T1[i]+T2[i]+((q1+q2)×2nmodM){Carrysaveaddition}{Theresidue((q1+q2)×2nmodM)isprecomputed}{q1,q2}={C1[i]≫(n-1),C2[i]≫(n-1)}{q1 and q2 are the upper 2 bits of C1[i] and C2[i] respectively.}{C1[i],C2[i]}={2C1[i] & (2n-1),2C2[i] & (2n-1)}{Settheupper2bitsofC1[i]andC2[i]tozero}end for{C1[0],C2[0]}={2C1[0],2C2[0]}{Rightshiftsotheyarebothn-1bits}C=C1[0]+C2[0]+((q1+q2)×2n-1modM)Figure 4
New sum of residues modular multiplier architecture.The LUTs have a 4-bit input and ann-bit output so that a (24×n)-bit ROM can be used. Moreover, note that the sum of (q1+q2) is at most 110, which occurs when (q1 and q2) are both 11. This implies that the possible sum of (q1+q2) is in the range from 000 to 110, which has 7 values only. Therefore, a ROM with a further reduced size of (7×n) bits can be used for (q1+q2)×2nmodM. For example, a 128-bit modular multiplier only needs a 1K-bit ROM, which is reasonable for a RNS channel modular multiplier.Figure5 shows  an example of the new algorithm for the case r=2, n=4, A=15=(1111)2, B=11=(1011)2, and M=9=(1001)2. It is noted that at the last step, a second LUT of the same size is needed. Also, because the output C from the 4-bit CPA is at most 5 bits long, the final subtraction might not be necessary if a n+1-bit C is acceptable, as the case in quite a few other algorithms. Even if a 4-bit C is required, only one subtraction will do.Figure 5
An example for the new algorithmn=4, A=(1111)2, B=(1011)2, and M=(1001)2.


## 4.4. Higher Radix

High radix is another popular technique that has been adopted by other algorithms [17, 24]. It also contributes to the new sum of residues algorithm. A radix-r version of the algorithm can be produced as in Figure 6. If r=2k, this version executes in n/k iterations; however,  a larger LUT and (n+k)-bit CSAs are required.Figure 6
New higher-radix sum of residues modular multiplier architecture.


## 5. Evaluation

### 5.1. Evaluation Environment

FPGA implementations have been prepared. A Xilinx Virtex2 FPGA was used as the implementation target. All the implementations have been performed using the Xilinx ISE environment using XST for synthesis and ISE standard tools for place and route with standard effort for all speed optimizations (see Table2).Pure delays of the combinatorial  circuit were measured excluding those between pads and pins. They were generated from the post-place and route static timing analyzer with a standard place and  route effort level.


### 5.2. Results

Implementation results are listed in Table1 for n=4 to n=24 at radix-2, the most popular word lengths of RNS channel modular multipliers [6, 9, 32]. The table includes results for the old architecture based on Tomlinson's algorithm (Figure 1) as well as for a carefully optimized Montgomery architecture.Table 1
Latency and space overhead of three interleaved modular multipliers.
ArchitectureFiguren = 4n = 8n = 12n = 16n = 24New sum of residuesFigure412.1 ns 35 slices22.3 ns 142 slices33.5 ns 346 slices48.4 ns 616 slices66.9 ns 1415 slicesTomlinsonFigure115.0 ns 17 slices27.3 ns 62 slices48.6 ns 158 slices72.5 ns 275 slices129.5 ns 607 slicesMontgomery16.6 ns 24 slices31.7 ns  84 slices50.1 ns   176 slices69.6 ns   300 slices101.2 ns  644 slicesTable 2Target FPGAVirtex2 XC2V1000 with a-6 speed grade, 1M gates, 5120 slices and  embedded 18×18  multipliersXilinx 6.1iXST-synthesisISE-place and routeOptimization goalSpeedLanguageVHDLThe Montgomery architecture have incorporated various published techniques for optimization. For example, the techniques in [3, 23] have been applied to improve performance by making the quotient digit selection step trivial and moving it from the critical path. The cost of these techniques is that they impose limits on the possible values of the modulus M which may impact on other enhancements such as the use of higher  radices. Consequently, the Montgomery architecture is interleaved, uses radix 2 and trivial quotient digit selection (as in [3, 33] described in Section 3) and was arrived at by varying these parameters to find the multiplier with lowest delay.These multipliers are compared with the new binary sum of residues architecture of Figure4. It can be seen that the new sum of residues modular multiplier is a competitive alternative implementation on FPGA. It demonstrates better timing performance than both Tomlinson's architecture and the Montgomery architecture although its hardware cost is the highest among the three.


## 5.1. Evaluation Environment

FPGA implementations have been prepared. A Xilinx Virtex2 FPGA was used as the implementation target. All the implementations have been performed using the Xilinx ISE environment using XST for synthesis and ISE standard tools for place and route with standard effort for all speed optimizations (see Table2).Pure delays of the combinatorial  circuit were measured excluding those between pads and pins. They were generated from the post-place and route static timing analyzer with a standard place and  route effort level.


## 5.2. Results

Implementation results are listed in Table1 for n=4 to n=24 at radix-2, the most popular word lengths of RNS channel modular multipliers [6, 9, 32]. The table includes results for the old architecture based on Tomlinson's algorithm (Figure 1) as well as for a carefully optimized Montgomery architecture.Table 1
Latency and space overhead of three interleaved modular multipliers.
ArchitectureFiguren = 4n = 8n = 12n = 16n = 24New sum of residuesFigure412.1 ns 35 slices22.3 ns 142 slices33.5 ns 346 slices48.4 ns 616 slices66.9 ns 1415 slicesTomlinsonFigure115.0 ns 17 slices27.3 ns 62 slices48.6 ns 158 slices72.5 ns 275 slices129.5 ns 607 slicesMontgomery16.6 ns 24 slices31.7 ns  84 slices50.1 ns   176 slices69.6 ns   300 slices101.2 ns  644 slicesTable 2Target FPGAVirtex2 XC2V1000 with a-6 speed grade, 1M gates, 5120 slices and  embedded 18×18  multipliersXilinx 6.1iXST-synthesisISE-place and routeOptimization goalSpeedLanguageVHDLThe Montgomery architecture have incorporated various published techniques for optimization. For example, the techniques in [3, 23] have been applied to improve performance by making the quotient digit selection step trivial and moving it from the critical path. The cost of these techniques is that they impose limits on the possible values of the modulus M which may impact on other enhancements such as the use of higher  radices. Consequently, the Montgomery architecture is interleaved, uses radix 2 and trivial quotient digit selection (as in [3, 33] described in Section 3) and was arrived at by varying these parameters to find the multiplier with lowest delay.These multipliers are compared with the new binary sum of residues architecture of Figure4. It can be seen that the new sum of residues modular multiplier is a competitive alternative implementation on FPGA. It demonstrates better timing performance than both Tomlinson's architecture and the Montgomery architecture although its hardware cost is the highest among the three.


## 6. Conclusions and Future Work

Sum of residues is a distinct class of modular multiplication that has been overlooked in recent years. We have shown that techniques pioneered for other modular multiplication algorithms, such as the use of redundant representations and higher radices, can also be applied to sum of residues. By doing this,  we have arrived at a new sum of residues modular multiplier that uses carry-save adders and redundant number representation to achieve a more parallel structure than previous versions. FPGA implementations of the new architecture demonstrate low latency relative to previous sum of residues and Montgomery architectures at the cost of increased space overhead.Future work will be focused on reducing the space overhead. More advanced programmable logic devices will be attempted to utilize hardware resources more efficiently. ASIC design will be investigated, where a lot of the hardware redundancy expects to be reduced. For example, our new CSA shown in Figure3 accepts one extra bit input without extra hardware resources needed. However, this benefit is hard to see in the FPGA implementation because splitting bits is impossible in the used configurable logic blocks (CLB) embedded on the FPGA. Nor do the embedded 18-bit multipliers. However, this gets easily illustrated in an ASIC implementation. Therefore, the new sum of residues modular multiplication algorithm is expected to be suitable for an ASIC application.



---

*Source: 657076-2010-11-30.xml*