DESIGN OF HIGH-PERFORMANCE AND SCALABLE MONTGOMERY MODULAR MULTIPLIER CIRCUITS

Abstract

This patent discloses novel design and implementations of high-performance and scalable Montgomery modular multiplier circuits by utilizing and developing a combination of optimization techniques and dataflow transformations including use of carry-save compressions, multiplier decomposition using a radix of 2m, multiplicand decomposition using a radix of 2w, parallelization of computations of the quotient and intermediate results in each iteration of the Montgomery modular multiplication, replacement of multiplications and additions in each iteration with simple encoding and compression operations, and correction of potential overflows in intermediate results by doing a simple 2-bit addition.

Claims

1. A Montgomery modular multiplier circuit comprising at least one digital processing component which produces a modular multiplication result by (a) decomposing a multiplier into a group of words, each word containing a number of bits, and (b) calculating one or more intermediate results based on the one or more intermediate results from a previous iteration and a product of a multiplicand and each word of the multiplier in an outer loop iteration.

2. The Montgomery modular multiplier circuit of claim 1 wherein the one or more intermediate results in each outer loop iteration is decomposed into a number of parts where some parts are moved to the next outer loop iteration for processing.

3. The Montgomery modular multiplier circuit of claim 2, wherein carry-save compressors are used to replace multiplication operations to generate the one or more intermediate results.

4. The Montgomery modular multiplier circuit of claim 3 wherein: (a) the multiplicand is first left shifted by some number of bits and is then decomposed into a second group of words, each word containing a second number of bits, and (b) the one or more intermediate results in each outer loop iteration are calculated based on the one or more intermediate results from two previous outer loop iterations and products of each word of the multiplicand and one word of the multiplier in an inner iteration loop.

5. The Montgomery modular multiplier circuit of claim 1 wherein the modular multiplication result is produced by (a) decomposing the multiplier into the group of words, each word containing a number of bits, and (b) independently calculating two sets of one or more intermediate results based on two sets of one or more intermediate results from the previous iteration and the product of the multiplicand and each word of the multiplier in the outer loop iteration.

6. The Montgomery modular multiplier circuit of claim 5 wherein first encoding circuits are used to speed up calculation of any expression that may be modelled as the product of a sum of two integers with another integer.

7. The Montgomery modular multiplier circuit of claim 4 wherein: (a) the one or more intermediate results in each outer loop iteration are partitioned into two sets which can be calculated independently, (b) first encoding circuits are used to speed up the calculation of any expression that may be modelled as the product of a sum of two integers with another integer, and (c) second encoding circuits are used to decompose each of the intermediate results in a set of one or more intermediate results into two corresponding intermediate results.

8. The Montgomery modular multiplier circuit of claim 6 wherein: (i) the multiplicand is first left shifted by some number of bits and is then decomposed into a third group of words, each word containing a third number of bits, (ii) the one or more intermediate results in each outer loop iteration are calculated based on the two sets of one or more intermediate results from two previous outer loop iterations and products of each word of the multiplicand and one word of the multiplier in an inner iteration loop, and (iii) second encoding circuits are used to decompose each of the intermediate results in the set of one or more intermediate results into two corresponding intermediate results.

9. The Montgomery modular multiplier circuit of claim 1 wherein the modular multiplication result is an output value Z congruent to XYR.sup.−1 modM, wherein X is an (N+1)-bit wide multiplicand and Y is an (N+1)-bit wide multiplier with X and Y being integer numbers in the range [0,2M), M is an N-bit wide modulus, R is an integer that is a power of 2 such that R>M, and R.sup.−1 is a modular multiplicative inverse of R with respect to M, the Montgomery modular multiplier circuit using a first input r.sup.−1∈[0, M) and a second input M′∈[0, r) such that rr.sup.−1−MM′=1 with r=2.sup.m and wherein the least one digital processing component is configured to: a) decompose multiplier Y into n.sub.m=┌(N+m+2)/m┐ words of m bits each, pad (n.sub.m*m−N−1) zero's to the left of Y such that Y=Σ.sub.i=0.sup.n.sup.m Y.sub.i2.sup.im with Y.sub.i=Y[im+m−1: m] for 0≤i≤n.sub.m; and b) produce output value Z by iteratively calculating and combining XY.sub.ir.

10. The Montgomery modular multiplier circuit of claim 9 wherein the at least one digital processing component comprises: a) a plurality of processing elements (PEs) such that the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more second intermediate results from the (i−1)-st PE, and the value of XY.sub.ir; and b) a post-processing processing element which takes as input the intermediate results of the last two PEs and produces the output value Z.

11. The Montgomery modular multiplier circuit of claim 10 wherein a weighted sum of first intermediate results produced by the i-th PE is congruent to X(Σ.sub.j=0.sup.i Y.sub.j2.sup.jm)r.sup.−i.

12. The Montgomery modular multiplier circuit of claim 1 wherein the at least one digital processing component is further configured to: a) left shift multiplicand X by m bits to produce X′=Xr, pad (e*w−N−m−1) zero's to the left of X′, and decompose X′ into e=┌(N+2m+2)/w┐ words of w bits each such that X′=Σ.sub.j=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1; and b) produce output value Z by iteratively calculating and combining X′.sub.jY.sub.i.

13. The Montgomery modular multiplier circuit of claim 12 wherein the at least one digital processing component comprises: a) a plurality of processing elements (PEs) such that the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more intermediate results from the (i−1)-st PE, and the value of XY.sub.ir in e cycles, where in each cycle the i-th PE receives w bits of each intermediate result from the (i−2)-nd PE and the (i−1)-st PE, and produces w bits of the first intermediate results; and b) a post-processing processing element which takes intermediate results of the last two PEs and produces the output value Z in e cycles.

14. The Montgomery modular multiplier circuit of claim 12, wherein the data initiation latency is 1 cycle and wherein the Montgomery modular multiplier circuit is scalable.

15. The Montgomery modular multiplier circuit of claim 12, wherein there are two or more first intermediate results and two of the first intermediate results are decomposed into e=┌(N+2m+2)/w┐ words of w bits, where m≥2 and w≥2m.

16. The Montgomery modular multiplier circuit of claim 15, wherein at least one of the first intermediate results has zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1.

17. The Montgomery modular multiplier circuit of claim 15, wherein at least one of the first intermediate results has zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1.

18. The Montgomery modular multiplier circuit of claim 10, wherein integer multiplication operations are unrolled into partial products, addition operations that are required to sum partial products and other results are replaced with k-to-2 compressors where k indicates numbers of integers that need to be compressed successively.

19. The Montgomery modular multiplier circuit of claim 18, wherein the at least one digital processing component is further configured to pad (n.sub.m*m−(N+1)) zero's to the left of multiplier Y and decompose the padded Y into n.sub.m=┌(N+2m+2)/m┐ words of m bits each, such that Y=Σ.sub.i=0.sup.n.sup.m Y.sub.i2.sup.im with Y.sub.i=Y[im+m−1: m] for 0≤i≤n.sub.m, and wherein the at least one digital processing component comprises: a) a plurality of processing elements (PEs), the i-th PE producing first intermediate results based on intermediate results from the (i−2)-nd PE and the (i−1)-st PE and such that a weighted sum of intermediate results is congruent to X(Σ.sub.j=0.sup.i Y.sub.j2.sup.jm)r.sup.−i; and b) a post-processing processing element taking intermediate results of the last and next to the last PEs and producing the output value Z.

20. The Montgomery modular multiplier circuit of claim 18, wherein there are two or more first intermediate results and at least two of the first intermediate results are decomposed into e=┌(N+2m+2)/w┐ words of w bits, where m≥2 and w≥2m.

21. The Montgomery modular multiplier circuit of claim 20, wherein at least one of the first intermediate results has zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1.

22. The Montgomery modular multiplier circuit of claim 20, wherein at least one of the first intermediate results has zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1.

23. The Montgomery modular multiplier circuit of claim 19, wherein one of the intermediate results is a 1-bit value.

24. The Montgomery modular multiplier circuit of claim 18, wherein a Booth coding technique is used to speed up the compressors.

25. The Montgomery modular multiplier circuit of claim 19, wherein multiplicand X is left shifted by m bits to produce X′=Xr, padded with (e*w−m−(N+1)) zero's on the left, and the padded X′ is decomposed into e words of w bits each with such that X′=Σ.sub.j=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1) such that the PEs compute their first intermediate results by repeatedly calculating the product of X′.sub.jY.sub.i for different i and j indices, thereby, enabling design of PEs that are independent of value of N, and producing a scalable Montgomery modular multiplier circuit.

26. The Montgomery modular multiplier circuit of claim 25, wherein the data initiation latency is 1 cycle and wherein the Montgomery modular multiplier circuit is scalable.

27. The post-processing processing element of claim 25 repeatedly taking intermediate results of the last two PEs and producing the partial output value Z.

28. A Montgomery modular multiplier circuit, which calculates an output value Z congruent to XYR.sup.−1modM, wherein X is an N-bit multiplicand and Y is an N-bit multiplier with X and Y being integer numbers in the range [0, M), M is a N-bit wide modulus, R is an integer that is a power of 2 such that R>M, and R.sup.−1 is a modular multiplicative inverse of R with respect to M, Montgomery modular multiplier circuit receiving a first additional input r.sup.−1∈[0, M) and a second additional input M″∈[0, r.sup.2) such that r.sup.2r.sup.−1−MM″=1 with r=2.sup.m and comprises at least one digital processing component configured to: a) decompose multiplier Y into n.sub.m=┌N/m┐ words of m bits each, pad (n.sub.m*m−N) zero's to the left of Y such that Y=Σ.sub.i=0.sup.n.sup.m.sup.−1 Y.sub.i2.sup.im with Y.sub.i=Y[im+m−1: m] for 0≤i<n.sub.m; and b) produce output value Z by iteratively calculating and combining values of XY.sub.ir.sup.2.

29. The Montgomery modular multiplier circuit of claim 28 comprising: a) a digital processing component configured to produce two intermediate results independently of one another in the i-th iteration, wherein the two intermediate results are calculated based on the value of XY.sub.ir.sup.2 and the corresponding two intermediate results produced in the (i−1)-st iteration; and b) a post-processing processing element which takes intermediate results of the last iteration as input and produces the output value Z.

30. The Montgomery modular multiplier circuit of claim 29 wherein one intermediate result produced in the i-th iteration is congruent to X(Σ.sub.j=0.sup.i Y.sub.ir.sup.j)r.sup.−(i-1)modM where r.sup.−(i-1) is the multiplicative inverse of r.sup.i−1modM.

31. The Montgomery modular multiplier circuit of claim 20 further comprising a first encoder circuit, which calculates (t+1)-bit outputs â and {circumflex over (b)} from t-bit inputs a and b, wherein t≥3. The encoder circuit ensuring that v.sub.â+v.sub.{circumflex over (b)}=a+b where v.sub.â=â[t]2.sup.t−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 â[i]2.sup.i and v.sub.{circumflex over (b)}={circumflex over (b)}[t]2.sup.t−{circumflex over (b)}[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 {circumflex over (b)}[i]2.sup.i, and comprising at least one digital processing component configured to: a) calculate a 3-bit intermediate result d as d[2: 0]=a[t−1: t−2]+b[t−1: t−2]+(a[t−3]ANDb[t−3]); b) if t≥4, calculate â[t−4: 0]=a[t−4: 0] and {circumflex over (b)}[t−4: 0]=b[t−4: 0]; c) calculate â[t−3]=a[t−3]XORb[t−3]; â[t−2]=d[0]; â[t−1]=d[1]; â[t]=d[2]; and d) calculate {circumflex over (b)}[t−1: t−3]=0; {circumflex over (b)}[t]=d[1].

32. The Montgomery modular multiplier circuit of claim 31, further comprising a second encoder circuit which calculates (t+1)-bit outputs ã and {tilde over (b)} from t-bit inputs a and b and 1-bit input c, where t≥2. The encoder circuit ensuring that v.sub.ã+v.sub.{tilde over (b)}=a+b+c where v.sub.ã=Σ.sub.i=0.sup.t/2 ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 ã[2i+1]2.sup.2i+1 and v.sub.{tilde over (b)}=Σ.sub.i=0.sup.t/2 {tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i+1]2.sup.2i+1, and comprising at least one digital processing component configured to: a) encode a[1: 0], b[1: 0], and c to generate outputs c.sub.out.sup.(0), d.sup.(0), and e.sup.(0); c) encode a[2i+1: 2i], b[2i+1: 2i], and c.sub.out.sup.(i−1) to generate outputs c.sub.out.sup.(i), d.sup.(i), and e.sup.(i) for 0<i≤t/2−1; d) calculate ã[2i+1: 2i]=d.sup.(i) for 0≤i≤t/2−1; ã[t]=c.sub.out.sup.(t/2-1); and e) calculate {tilde over (b)}[2i+2]=e.sup.(i) for 0≤i≤t/2−1.

33. The Montgomery modular multiplier circuit of claim 32 wherein: the digital processing component produces two groups of intermediate results independently of one another in the i-th iteration; the two groups of intermediate results produced in i-th iteration are calculated based on the value of X{tilde over (Y)}.sub.ir.sup.2 and the corresponding two groups of intermediate results produced in the (i−1)-st iteration wherein each group contains three intermediate results and {tilde over (Y)}.sub.i=Y.sub.i−Y.sub.i[m−1]r+Y.sub.i−1[m−1]; the first encoder circuit and the second encoder circuit accelerate calculation of intermediate results in the i-th iteration; and the post-processing processing element takes intermediate results of the last iteration as input and produces the output value Z.

34. The Montgomery modular multiplier circuit of claim 33 wherein a weighted sum of first intermediate results produced in the i-th iteration is congruent to X(Σ.sub.j=0.sup.i Y.sub.ir.sup.j)r.sup.−(i-1)modM where r.sup.−(i-1) is the multiplicative inverse of r.sup.1-1modM.

35. The Montgomery modular multiplier circuit of claim 33 wherein X is an (N+1)-bit multiplicand and Y is an (N+1)-bit multiplier with X and Y being integer numbers in the range [0,2M) wherein: the number of iterations d is at least ┌(N+4)/m┐ and R is r.sup.d-2; and the post-processing processing element which takes intermediate results of the last iteration as input and produces the output value Z.

36. The Montgomery modular multiplier circuit of claim 35 wherein the at least one digital processing component wherein: the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more second intermediate results from the (i−1)-st PE, and the value of X{tilde over (Y)}.sub.ir.sup.2; and the post-processing processing element which takes as input the intermediate results of the last two PEs and produces the output value Z.

37. The Montgomery modular multiplier circuit of claim 36, wherein there are two or more first intermediate results and two of the first intermediate results are decomposed into e=┌(N+2m+3)/w┐ words where w≥3m.

38. The Montgomery modular multiplier circuit of claim 37, wherein at least one of the first intermediate results has zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1.; and at least one of the first intermediate results has a tail bit at bit positions iw for 0≤i≤e−1.

39. The Montgomery modular multiplier circuit of claim 37, wherein at least one of the first intermediate results has zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1; and the weight of bit positions iw for 0≤i≤e−1 is −2.sup.iw.

40. The Montgomery modular multiplier circuit of claim 36 whereby multiplicand X is left shifted by 2m bits to produce X′=Xr.sup.2, padded with (e*w−N−m−1)) zero's on the left, and the padded X′ is decomposed into e words of w bits each with such that X′=Σ.sub.j=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1) such that the PEs compute their first group of intermediate results by repeatedly calculating the product of X′.sub.jY.sub.i for different i and j indices, thereby, enabling design of PEs that are independent of value of N, and producing a scalable Montgomery modular multiplier circuit.

41. The Montgomery modular multiplier circuit of claim 40 where the data initiation latency is 1 cycle and wherein the Montgomery modular multiplier circuit is scalable.

42. The Montgomery modular multiplier circuit of claim 40 wherein post-processing repeatedly takes intermediate results of the last two PEs and producing the partial output value Z.

43. The Montgomery modular multiplier circuit of claim 40 wherein post-processing repeatedly is designed into a pipeline with L stages where the data initiation latency is L cycle.

44. An encoder circuit, which calculates (t+1)-bit outputs â and {circumflex over (b)} from t-bit inputs a and b, wherein t≥3. The encoder circuit ensuring that v.sub.â+v.sub.{circumflex over (b)}=a+b where v.sub.â=â[t]2.sup.t−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 â[i]2.sup.i and v.sub.{circumflex over (b)}={circumflex over (b)}[t]2.sup.t−{circumflex over (b)}[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 {circumflex over (b)}[i]2.sup.i, and comprising at least one digital processing component configured to: a) calculate a 3-bit intermediate result d as d[2: 0]=a[t−1: t−2]+b[t−1: t−2]+(a[t−3]ANDb[t−3]); b) if t≥4, calculate â[t−4: 0]=a[t−4: 0] and {circumflex over (b)}[t−4: 0]=b[t−4: 0]; c) calculate â[t−3]=a[t−3]XORb[t−3]; â[t−2]=d[0]; â[t−1]=d[1]; â[t]=d[2]; and d) calculate {circumflex over (b)}[t−1: t−3]=0; {circumflex over (b)}[t]=d[1].

45. The encoder circuit of claim 44 wherein v.sub.â[t-1:0]+v.sub.{circumflex over (b)}[t-1:0] is congruent to a+bmod2.sup.t with v.sub.â[t-1:0]=−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 â[i]2.sup.i and v.sub.{circumflex over (b)}[t-1:0]=−{circumflex over (b)}[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 {circumflex over (b)}[i]2.sup.i.

46. An encoder circuit, which calculates 3-bit outputs â and {circumflex over (b)} from 2-bit inputs a and b, wherein the encoder circuit ensures that v.sub.â+v.sub.{circumflex over (b)}=a+b with v.sub.â=4â[2]−2â[1]+â[0] and v.sub.{circumflex over (b)}=4{circumflex over (b)}[2]−2{circumflex over (b)}[1]+{circumflex over (b)}[0], and comprising at least one digital processing component configured to: calculate a 3-bit intermediate result d as d [2: 0]=a+b; calculate â=d; and calculate {circumflex over (b)}[1: 0]=0; {circumflex over (b)}[2]=d[1].

47. The encoder circuit of claim 46 wherein v.sub.â[1:0]+v.sub.{circumflex over (b)}[1:0] is congruent to a+bmod4 with v.sub.â[1:0]=−2â[1]+â[0] and v.sub.{circumflex over (b)}[1:0]=−2{circumflex over (b)}[1]+{circumflex over (b)}[0].

48. An encoder circuit, which calculates 1-bit outputs c.sub.out and e and a 2-bit output d from 2-bit inputs a and b, and 1-bit input c.sub.in. The encoder circuit ensures that 4c.sub.out+4e−2d[1]+d[0]=a+b+c and comprises at least one digital processing component configured to: calculate a 2-bit value as 2c [1]+d[0]=a[0]+b[0]+c.sub.in; calculate c.sub.out=a[1]ANDb[1]; calculate d[1]=a[1]XORb[1]XORc[1]; and calculate e=a[1]XORb[1]ORc[1].

49. The encoder circuit of claim 48, configured to calculate (t+1)-bit outputs ã and {tilde over (b)} from t-bit inputs a and b and 1-bit input c, where t≥2. The encoder circuit ensuring that v.sub.ã+v.sub.{tilde over (b)}=a+b+c where v.sub.â=Σ.sub.i=0.sup.t/2 ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 ã[2i+1]2.sup.2i+1 and v.sub.{tilde over (b)}=Σ.sub.i=0.sup.t/2 {tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i+1]2.sup.2i+1, and comprising at least one digital processing component configured to: a) encode a[1: 0], b[1: 0], and c to generate outputs c.sub.out.sup.(0), d.sup.(0), and e.sup.(0); c) encode a[2i+1: 2i], b[2i+1: 2i], and c.sub.out.sup.(i−1) to generate outputs c.sub.out.sup.(i), d.sup.(i), and e.sup.(i) for 0<i≤t/2−1; d) calculate ã[2i+1: 2i]=d.sup.(i) for 0≤i≤t/2−1; ã[t]=c.sub.out.sup.(t/2-1); and e) calculate {tilde over (b)}[2i+2]=e.sup.(i) for 0≤i≤t/2−1.

50. The encoder circuit of claim 49 wherein if parameter t is odd, inputs a and b are padded by one 0 on the left.

51. The encoder circuit of claim 49 wherein v.sub.ã[t-1:0]+v.sub.{tilde over (b)}[t-1:0] is congruent to a+bmod2.sup.t with v.sub.ã[t-1:0]=Σ.sub.i=0.sup.t/2-1 ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 ã[2i+1]2.sup.2i+1 and v.sub.{tilde over (b)}[t-1:0]=Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i+1]2.sup.2i+1.

52. The encoder circuit of claim 49 wherein v.sub.ã+v.sub.{tilde over (b)}−c is equal to v.sub.â+v.sub.{circumflex over (b)}.

53. The encoder circuit of claim 49 wherein v.sub.ã[t-1:0]+v.sub.{tilde over (b)}[t-1:0]−c is equal to v.sub.â[t-1:0]+v.sub.{circumflex over (b)}[t-1:0].

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0042] For a further understanding of the nature, objects, and advantages of the present disclosure, reference should be had to the following detailed description, read in conjunction with the following drawings, wherein like reference numerals denote like elements and wherein:

[0043] FIGS. 1a, 1b, and 1c. Embodiments of Montgomery modular multiplier circuits.

[0044] FIGS. 1d, 1e, and 1f. Decoders that is used in the Montgomery modular multiplier circuits.

[0045] FIG. 2. Example of i-th outer loop iteration when N=8, w=8, and m=2.

[0046] FIG. 3. Data Dependency Graph of the MWR2tm Algorithm.

[0047] FIGS. 4a and 4b. Schedule for N=6, w=4, and m=2 with (a) p=3 and (b) p=2.

[0048] FIG. 5. Internal Design of the Processing Element (PE) for the MWR2tm realization with L=1.

[0049] FIG. 6. Proposed Radix 2.sup.m Scalable Architecture of Montgomery Modular Multiplication.

[0050] FIG. 7. Special Compression for 5-to 2 in PE.

[0051] FIG. 8. PEc Diagram for C Task.

[0052] FIG. 9. Special Compression for 8-to-2 in PEc.

[0053] FIGS. 10a and 10b. Time Latency of the Proposed Montgomery MM Design Presuming N=1,024 with Actual Values of (a) N≤1,024 and (b) N≥1,024.

[0054] FIG. 11. Throughput of the Proposed Montgomery MM Design Presuming N=1,024 and with Actual Values of N≥1,024.

[0055] FIG. 12. Example of Encode when m=8.

[0056] FIG. 13. Model to group k=2 bits.

[0057] FIG. 14. Example of EncodeSN when m=8.

[0058] FIG. 15. Computing q.sup.(i).

[0059] FIG. 16. 8-bit signed multiplication with radix-4 modified Booth Coding.

[0060] FIG. 17. Data model to accurately represent Z by Z.sub.S, Z.sub.C, and Z.sub.carry.

[0061] FIG. 18. Compute Z.sup.(i).

[0062] FIG. 19. Block-level diagram for the hardware implementation of the proposed Montgomery modular multiplication.

[0063] FIG. 20. Data Dependency Graph.

[0064] FIGS. 21a and 21b. Schedule for N=8, w=6, and m=2 with (a) p=3 and (b) p=2

[0065] FIG. 22. Internal Design of the Processing Element (PE) for the MWR2tm realization with L=1.

[0066] FIG. 23. Proposed Radix 2.sup.m Scalable Architecture of Montgomery Modular Multiplication

[0067] FIG. 24. Overflow when computing ZSME.sub.e-1/ZCME.sub.e-1 by truncation when m=4.

[0068] FIG. 25. Data model for overflow correction.

[0069] FIG. 26. PEc Diagram for C task.

[0070] FIG. 27. Table 1: Area and Performance of the Proposed Montgomery Modular Multiplication Design for w and m, when the Modulus M Has N=1024 Bits

[0071] FIG. 28. Table 2: Comparisons of Different Montgomery Modular Multiplication with N=1024 and N=2048.

[0072] FIG. 29. Table 3: Area and Performance of Different Montgomery Modular Multiplication Designs on Virtex-7 FPGA.

DETAILED DESCRIPTION

[0073] Reference will now be made in detail to presently preferred embodiments and methods of the present invention, which constitute the best modes of practicing the invention presently known to the inventors. The Figures are not necessarily to scale. However, it is to be understood that the disclosed embodiments are merely exemplary of the invention that may be embodied in various and alternative forms. Therefore, specific details disclosed herein are not to be interpreted as limiting, but merely as a representative basis for any aspect of the invention and/or as a representative basis for teaching one skilled in the art to variously employ the present invention.

[0074] It is also to be understood that this invention is not limited to the specific embodiments and methods described below, as specific components and/or conditions may, of course, vary. Furthermore, the terminology used herein is used only for the purpose of describing particular embodiments of the present invention and is not intended to be limiting in any way.

[0075] It must also be noted that, as used in the specification and the appended claims, the singular form “a,” “an,” and “the” comprise plural referents unless the context clearly indicates otherwise. For example, reference to a component in the singular is intended to comprise a plurality of components.

[0076] The term “comprising” is synonymous with “including,” “having,” “containing,” or “characterized by.” These terms are inclusive and open-ended and do not exclude additional, unrecited elements or method steps.

[0077] The phrase “consisting of” excludes any element, step, or ingredient not specified in the claim. When this phrase appears in a clause of the body of a claim, rather than immediately following the preamble, it limits only the element set forth in that clause; other elements are not excluded from the claim as a whole.

[0078] The phrase “consisting essentially of” limits the scope of a claim to the specified materials or steps, plus those that do not materially affect the basic and novel characteristic(s) of the claimed subject matter.

[0079] With respect to the terms “comprising,” “consisting of,” and “consisting essentially of,” where one of these three terms is used herein, the presently disclosed and claimed subject matter can include the use of either of the other two terms.

[0080] It should also be appreciated that integer ranges explicitly include all intervening integers. For example, the integer range 1-10 explicitly includes 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. Similarly, the range 1 to 100 includes 1, 2, 3, 4 . . . 97, 98, 99, 100. Similarly, when any range is called for, intervening numbers that are increments of the difference between the upper limit and the lower limit divided by 10 can be taken as alternative upper or lower limits. For example, if the range is 1.1. to 2.1 the following numbers 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, and 2.0 can be selected as lower or upper limits.

[0081] When referring to a numerical quantity, in a refinement, the term “less than” includes a lower non-included limit that is 5 percent of the number indicated after “less than.” A lower non-includes limit means that the numerical quantity being described is greater than the value indicated as a lower non-included limited. For example, “less than 20” includes a lower non-included limit of 1 in a refinement. Therefore, this refinement of “less than 20” includes a range between 1 and 20. In another refinement, the term “less than” includes a lower non-included limit that is, in increasing order of preference, 20 percent, 10 percent, 5 percent, 1 percent, or 0 percent of the number indicated after “less than.”

[0082] The term “electronic component” refers is any physical entity in an electronic device or system used to affect electron states, electron flow, or the electric fields associated with the electrons. Examples of electronic components include, but are not limited to, capacitors, inductors, resistors, thyristors, diodes, transistors, etc. Electronic components can be passive or active.

[0083] The term “electronic device” or “system” refers to a physical entity formed from one or more electronic components to perform a predetermined function on an electrical signal.

[0084] It should be appreciated that in any figures for electronic devices, a series of electronic components connected by lines (e.g., wires) indicates that such electronic components are in electrical communication with each other. Moreover, when lines directed connect one electronic component to another, these electronic components can be connected to each other as defined above.

[0085] The processes, methods, or algorithms disclosed herein can be deliverable to/implemented by a processing device, controller, or computer, which can include any existing programmable electronic control unit or dedicated electronic control unit. Similarly, the processes, methods, or algorithms can be stored as data and instructions executable by a controller or computer in many forms including, but not limited to, information permanently stored on non-writable storage media such as ROM devices and information alterably stored on writeable storage media such as floppy disks, magnetic tapes, CDs, RAM devices, and other magnetic and optical media. The processes, methods, or algorithms can also be implemented in an executable software object. Alternatively, the processes, methods, or algorithms can be embodied in whole or in part using suitable hardware components, such as Application Specific Integrated Circuits (ASICs), Field-Programmable Gate Arrays (FPGAs), state machines, controllers or other hardware components or devices, or a combination of hardware, software and firmware components.

[0086] Throughout this application, where publications are referenced, the disclosures of these publications in their entireties are hereby incorporated by reference into this application to more fully describe the state of the art to which this invention pertains.

[0087] Abbreviation:

[0088] “FPGAs” means Field-Programmable Gate Arrays.

[0089] “PE” means processing element.

[0090] The terms “processing element” and “processing component” refers to a computer processor (e.g., CPU), programmable logic array, Field-Programmable Gate Array, or any assembly of logic circuits designed to implement the predetermined steps set forth below.

[0091] Referring to FIGS. 1a, 1b, and 1c, embodiments of a Montgomery modular multiplier circuit are provided. The Montgomery modular multiplier 10 includes at least one digital processing component 12, which produces a modular multiplication result by (i) decomposing the multiplier into a group of words, each word containing a number of bits, and (ii) calculating one or more intermediate results based on the one or more intermediate results from a previous iteration and a product of the multiplicand and each word of the multiplier in an outer loop iteration. Montgomery modular multiplier circuit 10 can also include includes a plurality of processing elements (PEs) 14.sup.i and post-processing processing element 16. The processing elements (PEs) 14.sup.i include addition block 18 and compressor bock 22 and post-processing processing element 16 includes addition block 18, where i is an integer label for the processing elements. Typically, i runs from 1 to the total number of processing elements.

[0092] In a variation, the one or more intermediate results in each outer loop iteration is decomposed into a number of parts where some of the said parts are moved to a next iteration for processing. In a refinement, carry-save compressors 24 within compressor block 22 are used to replace multiplication operations to generate one or more intermediate results. In a further refinement, at least one digital processing component 12 is configured such that (i) the multiplicand is first left-shifted by some number of bits and is then decomposed into a second group of words, each word containing a second number of bits, and (ii) the one or more intermediate results in each outer loop iteration are calculated based on the one or more intermediate results from two previous outer loop iterations and products of each word of the multiplicand and one word of the multiplier in an inner iteration loop.

[0093] In a variation, the at least one digital processing component 12 is configured such that modular multiplication result is produced by (i) decomposing the multiplier into a group of words, each word containing a number of bits, and (ii) independently calculating two sets of one or more intermediate results based on the two sets of one or more intermediate results from a previous iteration and a product of the multiplicand and each word of the multiplier in an outer loop iteration. In a refinement, encoding circuit 20 are used to speed up the calculation of any expression that may be modeled as the product of a sum of two integers with another integer.

[0094] In another variation, at least one digital processing component 12 is configured such that (i) the one or more intermediate results in each outer loop iteration are partitioned into two sets which can be calculated independently, (ii) first encoding circuits are used to speed up the calculation of any expression that may be modeled as the product of a sum of two integers with another integer, and (iii) second encoding circuits are used to decompose each of the intermediate results in the set of one or more intermediate results into two corresponding intermediate results.

[0095] In another variation, the at least one digital processing component 12 is configured such that (i) the multiplicand is first left shifted by some number of bits and is then decomposed into a third group of words, each word containing a third number of bits, (ii) the one or more intermediate results in each outer loop iteration are calculated based on the two sets of one or more intermediate results from two previous outer loop iterations and products of each word of the multiplicand and one word of the multiplier in an inner iteration loop, and (iii) second encoding circuits are used to decompose each of the intermediate results in the set of one or more intermediate results into two corresponding intermediate results.

[0096] Referring to FIG. 1a, Montgomery modular multiplier circuit calculates an output value Z congruent to XYR.sup.−1modM, wherein X is an (N+1)-bit wide multiplicand and Y is an (N+1)-bit wide multiplier with X and Y being integer numbers in the range [0,2M), M is an N-bit wide modulus, R is an integer that is a power of 2 such that R>M, and R.sup.−1 is a modular multiplicative inverse of R with respect to M, the Montgomery modular multiplier circuit using a first input r.sup.−1∈[0, M) and a second input M′∈[0, r) such that rr.sup.−1−MM′=1 with r=2.sup.m. The Montgomery modular multiplier circuit 10 includes at least one digital processing component configured 12 to: a) decompose multiplier Y into n.sub.m=┌(N+m+2)/m┐ words of m bits each, pad (n.sub.m*m−N−1) zero's to the left of Y such that Y=Σ.sub.i=0.sup.n.sup.m Y.sub.i2.sup.im with Y.sub.i=Y[im+m−1: m] for 0≤i≤n.sub.m; and b) produce output value Z by iteratively calculating and combining XY.sub.ir.

[0097] Still referring to FIG. 1a, the at least one digital processing component 12 includes a plurality of processing elements (PEs) 14.sup.i such that the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more second intermediate results from the (i−1)-st PE, and the value of XY.sub.ir. The at least one digital processing component 12 also includes a post-processing processing element 16 which takes as input the intermediate results of the last two PEs and produces the output value Z. A weighted sum of first intermediate results produced by the i-th PE is congruent to X(Σ.sub.j=0.sup.i Y.sub.j2.sup.jm)r.sup.−i.

[0098] In a variation, the at least one digital processing component 12 is further configured to:

[0099] a) left shift multiplicand X by m bits to produce X′=Xr, pad (e*w−N−m−1) zero's to the left of X′, and decompose X′ into e=┌(N+2m+2)/w┐ words of w bits each such that X′=Σ.sub.j=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1; and

[0100] b) produce output value Z by iteratively calculating and combining X′.sub.jY.sub.i.

[0101] In a refinement thereof, the at least one digital processing component 12 comprises:

[0102] a) a plurality of processing elements (PEs) such that the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more intermediate results from the (i−1)-st PE, and the value of XY.sub.ir in e cycles, where in each cycle the i-th PE receives w bits of each intermediate result from the (i−2)-nd PE and the (i−1)-st PE, and produces w bits of the first intermediate results; and

[0103] b) a post-processing PE which takes intermediate results of the last two PEs and produces the output value Z in e cycles.

[0104] In a refinement, the data initiation latency is 1 cycle and wherein the Montgomery modular multiplier circuit is scalable.

[0105] In a variation, two or more first intermediate results and two of the first intermediate results are decomposed into e=┌(N+2m+2)/w┐ words of w bits, where m≥2 and w≥2m. In a refinement, at least one of the first intermediate results has zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1. In another refinement, at least one of the first intermediate results has zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1.

[0106] In another variation, integer multiplication operations are unrolled into partial products, addition operations that are required to sum partial products and other results are replaced with k-to-2 compressors where k indicates numbers of integers that need to be compressed successively. In a refinement, the at least one digital processing component is further configured to pad (n.sub.m*m−(N+1)) zero's to the left of multiplier Y and decompose the padded Y into n.sub.m=┌(N+2m+2)/m┐ words of m bits each, such that Y=Σ.sub.i=0.sup.n.sup.m.sup.−1 Y.sub.i2.sup.im with Y.sub.i=Y [im+m−1: m] for 0≤i≤n.sub.m−1. The at least one digital processing component includes:

[0107] a) a plurality of processing elements (PEs), the i-th PE producing first intermediate results based on intermediate results from the (i−2)-nd PE and the (i−1)-st PE and such that a weighted sum of intermediate results is congruent to X(Σ.sub.j=0.sup.i Y.sub.j2.sup.jm)r.sup.−i; and

[0108] b) a post-processing PE taking intermediate results of the last and next to the last PEs and producing the output value Z. In a refinement thereof, there are two or more first intermediate results and at least two of the first intermediate results are decomposed into e=┌(N+2m+2)/w┐ words of w bits, where m≥2 and w≥2m. At least one of the first intermediate results can have zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1. Moreover, the at least one of the first intermediate results can have zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1. In a refinement, one of the intermediate results is a 1-bit value. In yet another refinement, a Booth coding technique is used to speed up the compressors.

[0109] In a refinement, multiplicand X is left shifted by m bits to produce X′=Xr, padded with (e*w−m−(N+1)) zero's on the left, and the padded X′ is decomposed into e words of w bits each with such that X′=Σ.sub.j=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1). The PEs compute their first intermediate results by repeatedly calculating the product of X′.sub.jY.sub.i for different i and j indices, thereby, enabling design of PEs that are independent of value of N, and producing a scalable Montgomery modular multiplier circuit. In a further refinement, the data initiation latency is 1 cycle. In a further refinement, the Montgomery modular multiplier circuit is scalable. Characteristically, the post-processing processing elements can repeatedly receive intermediate results of the last two PEs and produce the partial output value Z.

[0110] With reference to FIG. 1b, a Montgomery modular multiplier circuit is provided. The Montgomery modular multiplier circuit 10 calculates an output value Z congruent to XYR.sup.−1modM, wherein X is an N-bit multiplicand and Y is an N-bit multiplier with X and Y being integer numbers in the range [0, M), M is a N-bit wide modulus, R is an integer that is a power of 2 such that R>M, and R.sup.−1 is a modular multiplicative inverse of R with respect to M. Characteristically, the circuit uses a first additional input r.sup.−1∈[0, M) and a second additional input M″∈[0, r.sup.2) such that r.sup.2r.sup.−1−MM″=1 with r=2.sup.m. Montgomery modular multiplier circuit 10 includes at least one digital processing component 12 configured to:

[0111] a) decompose multiplier Y into n.sub.m=┌N/m┐ words of m bits each, pad (n.sub.m*m−N) zero's to the left of Y such that Y=Σ.sub.i=0.sup.n.sup.m.sup.−1 Y.sub.i2.sup.im with Y.sub.i=Y[im+m−1: m] for 0≤i<n.sub.m; and

[0112] b) produce output value Z by iteratively calculating and combining values of XY.sub.ir.sup.2.

[0113] Still referring to FIG. 1b, the Montgomery modular multiplier circuit 10 includes a digital processing element 14.sup.i configured to produce two intermediate results independently of one another in the i-th iteration, wherein the two intermediate results are calculated based on the value of XY.sub.ir.sup.2 and the corresponding two intermediate results produced in the (i−1)-st iteration. The Montgomery modular multiplier circuit also includes a post-processing processing element 16 which takes the intermediate results of the last iteration as input and produces the output value Z. In a refinement, one intermediate result produced in the i-th iteration is congruent to X(Σ.sub.j=0.sup.i Y.sub.jr.sup.j)r.sup.−(i-1) modM where r.sup.−(i-1) is the multiplicative inverse of r.sup.i−1modM.

[0114] Referring to FIG. 1c, in a the Montgomery modular multiplier circuit, the digital processing element(s) 14.sup.i produces two groups of intermediate results independently of one another in the i-th iteration. Moreover, the two groups of intermediate results produced in i-th iteration are calculated based on the value of X{tilde over (Y)}.sub.ir.sup.2 and the corresponding two groups of intermediate results produced in the (i−1)-st iteration wherein each group contains three intermediate results and {tilde over (Y)}.sub.i=Y.sub.i−Y.sub.i[m−1]r+Y.sub.i−1[m−1]. Encoder circuits 20 and 28 accelerate the calculation of intermediate results in the i-th iteration. Finally, a post-processing processing element which takes the intermediate results of the last iteration as input and produces the output value Z.

[0115] In a variation, a weighted sum of first intermediate results produced in the i-th iteration is congruent to X(Σ.sub.j=0.sup.i Y.sub.jr.sup.j)r.sup.−(i-1) modM where r.sup.−(i-1) is the multiplicative inverse of r.sup.i−1modM.

[0116] In another variation of the Montgomery modular multiplier circuit of FIG. 1c, X is an (N+1)-bit multiplicand and Y is an (N+1)-bit multiplier with X and Y being integer numbers in the range [0,2M) wherein the number of iterations d is at least ┌(N+4)/m┐ and R is r.sup.d-2; and post-processing processing element 16 takes the intermediate results of the last iteration as input and produces the output value Z.

[0117] In another variation, the at least one digital processing component 12 includes a plurality of processing elements 14.sup.i such that the i-th PE produces first intermediate results based on one or more intermediate results from the (i−2)-nd PE, one or more second intermediate results from the (i−1)-st PE, and the value of X{tilde over (Y)}.sub.ir.sup.2. The at least one digital processing component 12 also includes a post-processing element which takes as input the intermediate results of the last two PEs and produces the output value Z. In a refinement, there are two or more first intermediate results and two of the first intermediate results are decomposed into e=┌(N+2m+3)/w┐ words where w≥3m.

[0118] In a variation of FIG. 1c, the Montgomery modular multiplier circuit is configured such that at least one of the first intermediate results has zero's at bit positions iw to iw+w−m−1 for 0≤i≤e−1 and at least one of the first intermediate results has a tail bit at bit positions iw for 0≤i≤e−1.

[0119] In another variation of FIG. 1c, the Montgomery modular multiplier circuit is configured such that at least one of the first intermediate results has zero's at bit positions iw+w−m to iw+w−1 for 0≤i≤e−1 and the weight of bit positions iw for 0≤i≤e−1 is −2.sup.iw.

[0120] In another variation of FIG. 1c, the Montgomery modular multiplier circuit is configured such that multiplicand X is left shifted by 2m bits to produce X′=Xr.sup.2, padded with (e*w−N−m−1)) zero's on the left, and the padded X′ is decomposed into e words of w bits each with such that X′=Σ.sub.k=0.sup.e-1 X′.sub.j2.sup.jw with X′.sub.j=X′[jw+w−1: jw] for 0≤j≤e−1) such that the PEs compute their first group of intermediate results by repeatedly calculating the product of X′.sub.jY.sub.i for different i and j indices, thereby, enabling design of PEs that are independent of value of N, and producing a scalable Montgomery modular multiplier circuit. In a refinement, the data initiation latency is 1 cycle and the Montgomery modular multiplier circuit is scalable. In another refinement, the post-processing processing element 16 repeatedly receives intermediate results of the last two PEs and producing the partial output value Z. In a refinement, the processing elements are designed into a pipeline with L stages where the data initiation latency is L cycle.

[0121] With reference to FIG. 1d, an encoder circuit is provided. The endocoder 30 calculates (t+1)-bit outputs â and {circumflex over (b)} from t-bit inputs a and b, wherein t≥3. The encoder circuit ensuring that v.sub.â+v.sub.{circumflex over (b)}=a+b where v.sub.â=[t]2.sup.t−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 â[i]2.sup.i and v.sub.{circumflex over (b)}={circumflex over (b)}[t]2.sup.t−{circumflex over (b)}[t−1] 2.sup.t-1+Σ.sub.i=0.sup.t-1 {circumflex over (b)}[i] 2.sup.i. The encoder includes at least one digital processing component 32 configured to:

[0122] a) calculate a 3-bit intermediate result d as d[2: 0]=a[t−1: t−2]+b[t−1: t−2]+(a[t−3]ANDb[t−3]);

[0123] b) if t≥4, calculate â[t−4: 0]=a[t−4: 0] and {circumflex over (b)}[t−4: 0]=b[t−4: 0];

[0124] c) calculate â[t−3]=a[t−3]XORb[t−3]; â[t−2]=d[0]; â[t−1]=d[1]; â[t]=d[2]; and

[0125] d) calculate {circumflex over (b)}[t−1: t−3]=0; {circumflex over (b)}[t]=d[1].

[0126] In a refinement, v.sub.â[t-1:0]+v.sub.{circumflex over (b)}[t-1:0] is congruent to a+bmod2.sup.t with v.sub.â[t-1:0]=−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 â[i]2.sup.i and v.sub.{circumflex over (b)}[t-1:0]=−{circumflex over (b)}[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1 {circumflex over (b)}[i]2.sup.i.

[0127] In a variation, encoder 30 calculates 3-bit outputs â and {circumflex over (b)} from 2-bit inputs a and b, wherein the encoder circuit ensures that v.sub.â+v.sub.{circumflex over (b)}=a+b with v.sub.â=4â[2]−2â[1]+â[0] and v.sub.{circumflex over (b)}=4{circumflex over (b)}[2]−2{circumflex over (b)}[1]+{circumflex over (b)}[0]. The encoder includes at least one digital processing component 32 configured to calculate a 3-bit intermediate result d as d[2: 0]=a+b; calculate â=d; and calculate {circumflex over (b)}[1: 0]=0; {circumflex over (b)}[2]=d[1], In a variation, v.sub.â[1:0]+v.sub.{circumflex over (b)} [1:0] is congruent to a+bmod4 with v.sub.â[1:0]=−2â[1]+â[0] and v.sub.{circumflex over (b)}[1:0]=−2{circumflex over (b)}[1]+{circumflex over (b)}[0].

[0128] With reference to FIG. 1e, an encoder circuit is provided. The encoder 34 calculates 1-bit outputs c.sub.out and e and a 2-bit output d from 2-bit inputs a and b, and 1-bit input c.sub.in. The encoder circuit ensures that 4c.sub.out+4e−2d[1]+d[0]=a+b+c.sub.in. The encoder 34 includes at least one digital processing component 36 configured to calculate a 2-bit value as 2c[1]+d[0]=a[0]+b[0]+c.sub.in; calculate c.sub.out=a[1]ANDb[1]; calculate d[1]=a[1]XORb[1]XORc[1]; and calculate e=a[1]XORb[1]ORc[1].

[0129] With reference to FIG. 1f, encoder circuit 38 calculates (t+1)-bit outputs ã and {tilde over (b)} from t-bit inputs a and b and 1-bit input c, where t≥2. The encoder circuit ensuring that v.sub.ã+v.sub.{tilde over (b)}=a+b+c where v.sub.ã=Σ.sub.i=0.sup.t/2 ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 ã[2i+1]2.sup.2i+1 and v.sub.{tilde over (b)}=Σ.sub.i=0.sup.t/2 {tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i+1]2.sup.2i+1. The encoder includes one digital processing component 40 configured to:

[0130] a) encode a[1: 0], b[1: 0], and c to generate outputs c.sub.out.sup.(0), d.sup.(0), and e.sup.(0);

[0131] c) encode a[2i+1: 2i], b[2i+1: 2i], and c.sub.out.sup.(i−1) to generate outputs c.sub.out.sup.(i), d.sup.(i), and e.sup.(i) for 0<i≤t/2−1;

[0132] d) calculate ã[2i+1: 2i]=d.sup.(i) for 0≤i≤t/2−1; ã[t]=c.sub.out.sup.(t/2-1); and

[0133] e) calculate {tilde over (b)}[2i+2]=e.sup.(i) for 0≤i≤t/2−1. In a refinement, if parameter t is odd, inputs a and b are padded by one 0 on the left. In another refinement, v.sub.ã[t-1:0]+v.sub.{tilde over (b)}[t-1:0] is congruent to a+bmod2.sup.t with v.sub.ã[t-1:0]=Σ.sub.i=0.sup.t/2-1 ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 ã[2i+1]2.sup.2i+1 and v.sub.{tilde over (b)}[t-1:0]=Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1 {tilde over (b)}[2i+1]2.sup.2i+1.

[0134] In a refinement of the variation set forth above v.sub.ã+v.sub.{tilde over (b)}−c is equal to v.sub.â+v.sub.{circumflex over (b)}.

[0135] In a refinement of the variation set forth above, v.sub.ã[t-1:0]+v.sub.{tilde over (b)}[t-1:0]−c is equal to v.sub.â[t-1:0]+v.sub.{circumflex over (b)}[t-1:0].

[0136] Additional details of the invention are set forth below.

[0137] 1. Design of a Scalable Montgomery Modular Multiplier Circuit

[0138] 1.1 Fixed-Precision Optimization

[0139] Depending on the value of m, the high-radix Montgomery MM falls into one of two categories: (i) using explicit and expensive multiplication units when m is large, and (ii) replacing the explicit multiplications with simplified logic expressions when m is small. When m is large, e.g., m=16, prior art references have mainly focused on optimizing the MM time latency (product of cycle latency and clock period) and hardware cost (chip area) when they have two multiplication units [13, 24] or more than two multiplication units [16]. Considering area and delay, the bitwidth of the multiplication units cannot be made very large and are commonly chosen as 16 bits to maintain a good area-latency trade-off. When m is small, e.g., m=2, the multiplication unit can be explicitly simplified, for example by using modified Booth coding to reduce partial products. It would be desirable to develop a parametric high-radix (fixed-precision or scalable) Montgomery MM to support arbitrary m.

[0140] 1.1.1 Operation Rescheduling

[0141] The value of Z is updated twice in each iteration of realization 2, which in turn necessitates separate hardware resources and increases the data dependence. Fortunately, the FPR2tm realization can be rescheduled to address this shortcoming. More precisely, the accumulation of XY.sub.i+1 into Z.sup.(i+1) in the (i+1)-st iteration can be moved to the i-th iteration. Consequently, we can compute q.sup.(i)M and XY.sub.ir in parallel and accumulate them into Z.sup.(i).

[0142] Algorithm 5 is a modified version of the FPR2tm realization incorporating the rescheduling technique, where d is the number of iterations.

TABLE-US-00005   Realization 5 Modified FPR2tm version 1 Input: X, Y ∈ [0, 2M), odd M < 2.sup.N, r = 2.sup.m, d =   [00010]$.Math.\frac{N+m+2}{m}.Math.,R=r^{d-1},{\mathrm{rr}}^{-1}-{\mathrm{MM}}^{\prime }=1$ Output: Z ∈ [0, 2M)  1: Z.sup.(−1) = 0  2: for i = 0 to d − 1 do  3:  q.sup.(i) = (Z.sup.(i−1) mod r)M′ mod r  4:  Z.sup.(i) = (Z.sup.(i−1) + q.sup.(i)M + XY, r)/r  5: end for  6: Z = Z.sup.(d−1)  7: return Z

[0143] The value of d influences the upper bound of output Z. Indeed, we must find the minimum value of d to guarantee that the output Z lies in [0,2M) as explained next. Based on the equation in line 4 of the algorithm 5.1.1, we may explicitly compute Z.sup.(i) in terms of X, M, r, Y.sub.1, . . . , Y.sub.i, q.sup.(1), . . . , q.sup.(i), by recursively unfolding the Z.sup.(i) until Z.sup.(−1)=0 in (12). Note that q.sup.(0) is 0.

[00011]$\begin{array}{cc}{Z}^{\left(i\right)}r=Z^{\left(i-1\right)}+q^{\left(i\right)}M+{\mathrm{XY}}_{i}r& \left(12\right)\end{array}$$Z^{\left(i\right)}{r}^2=Z^{\left(i-1\right)}r+q^{\left(i\right)}\mathrm{Mr}+{\mathrm{XY}}_i{r}^2=q^{\left(i\right)}\mathrm{Mr}+{\mathrm{XY}}_i{r}^2+q^{\left(i-1\right)}M+{\mathrm{XY}}_{i-1}r$$.Math.$$Z^{\left(i\right)}{r}^{i+1}=M{.Math.}_{j=0}^i{q}^{\left(i\right)}{r}^j+\mathrm{Xr}{.Math.}_{j=0}^i{Y}_j{r}^j=\mathrm{Mr}{.Math.}_{j=0}^{i-1}{q}^{\left(j+1\right)}{r}^j+\mathrm{Xr}{.Math.}_{j=0}^i{Y}_j{r}^j$

[0144] In each iteration, we can scan m bits of the multiplier Y. When

[00012]$i\ge .Math.\frac{N+1}{m}.Math.,$

the multiplier Y is completely scanned, and we can find a tight upper bound of Z.sup.(i) as follows:

[00013]$\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i+1}=\mathrm{Mr}{.Math.}_{j=0}^{i-1}{q}^{\left(j+1\right)}{r}^j+\mathrm{Xr}{.Math.}_{j=0}^i{Y}_j{r}^j=\mathrm{Mr}{.Math.}_{j=0}^{i-1}{q}^{\left(j+1\right)}{r}^j+\mathrm{XYr}<\mathrm{Mr}\left(r-1\right)\frac{r^i-1}{r-1}+4M^{2}r<\left(r^{i+1}+4\mathrm{Mr}\right)M& \left(13\right)\end{array}$$Z^{\left(i\right)}<\left(1+\frac{4\mathrm{Mr}}{r^{i+1}}\right)M$

[0145] Therefore, the upper bound of Z.sup.(d-1) in the last iteration is

[00014]$Z^{\left(d-1\right)}<\left(1+\frac{4\mathrm{Mr}}{r^d}\right)M.$
md≥N+m+2  (14)

Following the equation 14, 4Mr<2.sup.N+m+2≤2.sup.md=r.sup.d so that we can guarantee that Z.sup.(d-1)<2M. In other words, if

[00015]$d\ge .Math.\frac{N+m+2}{m}.Math.,$

the output Z will always lie in [0,2M) as required.

[0146] 1.1.2 Intermediate Result Decomposition

[0147] During the computation of q.sup.(i), we only need the m least significant bits of Z.sup.(i−1) because of the operation Z.sup.(i−1)modr. When w≥2m, we can decompose Z into ZM and ZR as shown in (15) below. Since w−m≥m, we only need ZR (more precisely ZR.sub.0) to compute q.

Z=Σ.sub.i=0.sup.n.sup.w.sup.−1Z.sub.i2.sup.wi

Z.sub.i=ZM.sub.i+ZR.sub.i

ZM.sub.i=Z.sub.i[w−1: w−m].Math.2.sup.w-m

ZR.sub.i=Z.sub.i[w−m−1: 0]

Z=ZM+ZR

ZM=Σ.sub.i=0.sup.n.sup.w.sup.−1ZM.sub.i2.sup.wi

ZR=Σ.sub.i=0.sup.n.sup.w.sup.−1ZR.sub.i2.sup.wi  (15)

[0148] This decomposition seems of little value for the FPR2tm algorithm. However, it is an important observation in order to support the MWR2tm algorithm. As shown in reference [25], the MWR2t1 realization achieves L=1 when w≥2 and m=1. This article generalizes the aforesaid result and proves that the MWR2tm realization can also achieve L=1 when w≥2m for m≥1. We describe how the word decomposition is incorporated into the FPR2tm algorithm. In the 0-th iteration of realization 5, we can decompose Z.sup.(−1) into ZM.sup.(−1) and ZR.sup.(−1). Since the w−m least significant bits of ZM.sup.(−1) are 0, we have Z.sup.(−1)modr=ZR.sup.(−1)modr, and therefore we only need to use ZR.sup.(−1) to compute q.sup.(0).

[00016]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(-1\right)}& ={\mathrm{ZM}}^{\left(-1\right)}+{\mathrm{ZR}}^{\left(-1\right)}\\ q^{\left(0\right)}& =\left(Z^{-1)}\mathrm{mod}r\right)M^{\prime }\mathrm{mod}r\\ & =\left({\mathrm{ZR}}^{\left(-1\right)}\mathrm{mod}r\right)M^{\prime }\mathrm{mod}r\\ Z^{\left(0\right)}& =\left(Z^{-1)}+q^{\left(0\right)}M+{\mathrm{XY}}_{0}r\right)/r\\ & =\left({\mathrm{ZR}}^{-1}\right)+q^{\left(0\right)}M+{\mathrm{ZY}}_{0}r)/r+{\mathrm{ZM}}^{\left(-1\right)}/r\end{array}& \left(16\right)\end{array}$

[0149] We observe that ZM.sup.(−1)/r is not necessary to the required computations in the 0-th iteration and can be moved to the next iteration. We define Z.sub.new.sup.(0) as (ZR.sup.(−1)+q.sup.(0)M+XY.sub.0r)/r and decompose Z.sub.new.sup.(0) into ZM.sub.new.sup.(0) and ZR.sub.new.sup.(0). Z.sup.(0) may thus be rewritten as:

Z.sup.(0)=ZM.sub.new.sup.(0)+ZR.sub.new.sup.(0)+ZM.sup.(−1)/r  (17)

[0150] As before, ZM.sub.new.sup.(0) is not necessary to compute q.sup.(1), i.e.,

[00017]$\begin{array}{cc}\begin{array}{cc}{q}^{\left(1\right)}& =\left(\left({\mathrm{ZZ}}_{\mathrm{new}}^{\left(0\right)}+{\mathrm{ZM}}^{\left(-1\right)}/r\right)\mathrm{mod}r\right)M^{\prime }\mathrm{mod}r\\ Z^{\left(1\right)}& =\left(Z^{\left(0\right)}+q^{\left(1\right)}M+{\mathrm{XY}}_{1}r\right)/r\\ & =\left(\left({\mathrm{ZR}}_{\mathrm{new}}^{\left(0\right)}+{\mathrm{ZM}}^{\left(-1\right)}/r\right)+q^{\left(1\right)}M+{\mathrm{ZY}}_{1}r\right)/r\\ & +{\mathrm{ZM}}_{\mathrm{new}}^{\left(0\right)}/r\end{array}& \left(18\right)\end{array}$

[0151] Again, ZM.sub.new.sup.(0)/r is not necessary to the required computations in the 1-st iteration and can be moved to the second iteration. Since Z.sup.(−1)=0, we can define ZM.sub.new.sup.(−1)=ZM.sup.(−1)=0 and ZR.sub.new.sup.(−1)=ZR.sup.(−1)=0. Now then, for an arbitrary iteration i, we define Z.sub.new.sup.(i+1) as (ZR.sub.new.sup.(i)+(i+1) (i+1) (i+1) ZM.sub.new.sup.(i−1)/r+q.sup.(i+1)M+XY.sub.i+1)/r and decompose the new Z.sub.new.sup.(i+1) into ZM.sub.new.sup.(i+1) and ZR.sub.new.sup.(i+1).

[0152] Realization 6 is a modified version of the FPR2tm realization incorporating rescheduling and decomposition techniques. Note that the decomposition is quite easy to do in hardware.

TABLE-US-00006   Realization 6 Modified FPR2tm version 2 Input: X, Y ∈ [0, 2M), odd M < 2.sup.N, r = 2.sup.m, d =   [00018]$.Math.\frac{N+m+2}{m}.Math.,R=r^{d-1},{\mathrm{rr}}^{-1}-{\mathrm{MM}}^{\prime }=1$ Output: Z ∈ [0, 2M)  1: ZM.sup.(−2) = 0, ZM.sup.(−1) = 0, ZR.sup.(−1) = 0  2: for i = 0 to d − 1 do  3:  q.sup.(i) = ((ZM.sup.(i−2)/r + ZR.sup.(i−1)) mod r)M′ mod r  4:  Z.sup.(i) = ZM.sup.(i−2)/r + ZR.sup.(i−1) + q.sup.(i)M + XY.sub.ir  5:  (ZM.sup.(i), ZR.sup.(i)) = Decompose (Z.sup.(i)/r)  6: end for  7: Z = ZM.sup.(d−2)/r + ZM.sup.(d−1) + ZR.sup.(d−1)  8: return Z

[0153] 1.1.3 Elimination of Multiplication Operations

[0154] Even after rescheduling the original realization to remove some data dependencies, the performance of the FPR2tm realization continues to be limited by multiplications. Implementation of a multiplication operation involves generating partial products and summing them together. The timing critical paths of this operation are the carry chains for the addition of partial products. We can use a ternary tree arrangement of CSAs to speed up the compression. Meanwhile, if we use the carry-save form to pass partial results from one iteration to next and only deploy the addition at the end of the algorithm, the performance will improve further.

[0155] Instead of using Z.sup.(i), we can use the carry-save form ZS.sup.(i) and ZC.sup.(i) in line 4 of realization 6 and eliminate the final addition as detailed below.

Z.sup.(i)=ZS.sup.(i)+ZC.sup.(i)  (19)

[0156] Each of ZS.sup.(i) and ZC.sup.(i) consists of two parts:

ZS.sup.(i)=(ZS.sup.(i)>>m)r+ZS.sup.(i)mod r

ZC.sup.(i)=(ZC.sup.(i)>>m)r+ZC.sup.(i)mod r  (2)

[0157] where ZS.sup.(i)>>m=└ZS.sup.(i)/r┘, meaning that we right shift by m bits and thus ignore the least m significant bits of ZS.sup.(i). As a result, Z.sup.(i)/r can be rewritten as:

[00019]$\begin{array}{cc}\begin{array}{cc}\frac{Z^{\left(i\right)}}{r}& =\left({\mathrm{ZS}}^{\left(i\right)}>>m\right)+\left({\mathrm{ZC}}^{\left(i\right)}>>m\right)\\ & +\frac{{\mathrm{ZS}}^{\left(i\right)}\mathrm{mod}r+{\mathrm{ZC}}^{\left(i\right)}\mathrm{mod}r}{r}\end{array}& \left(21\right)\end{array}$

[0158] Based on the modular definition, we have

0≤ZS.sup.(i)mod r<r,0≤ZC.sup.(i)mod r<r  (22)

[0159] Since Z.sup.(i) is a multiple of r, (ZS.sup.(i)modr+ZC.sup.(i)modr) can only be either 0 or r. When ZC.sup.(i)modr=0, we have to choose ZS.sup.(i)modr=0 since ZS.sup.(i)modr cannot be r. When ZC.sup.(i)modr≠0, we have to choose ZS.sup.(i)modr=r−ZC.sup.(i)modr≠0 since ZC.sup.(i)modr cannot be negative. We may define the indicator c.sup.(i) to represent the (ZS.sup.(i)modr+ZC.sup.(i)modr)/r as follows (Notice that it is also correct to use ZS.sup.(i)modr to define c.sup.(i)). An indicator 1(x)=1 when the condition x is true and 0 otherwise.

[00020]$\begin{array}{cc}\begin{array}{c}{c}^{\left(i\right)}=(\begin{array}{cc}1& \mathrm{if}{\mathrm{ZC}}^{(i\left(\right)}\mathrm{mod}r\ne 0\\ 0& \mathrm{otherwise}\end{array}\\ =1\left({\mathrm{ZC}}^{\left(i\right)}\mathrm{mod}r\ne 0\right)\end{array}& \left(23\right)\end{array}$

[0160] In summary, Z.sup.(i)/r in line 5 of realization 6 may be replaced by the summation of ZS.sup.(i)>>m, ZC.sup.(i)>>m, and c.sup.(i). Moreover, ZS.sup.(i)>>m and ZC.sup.(i)>>m can be decomposed into (ZSM.sup.(i), ZSR.sup.(i)) and (ZCM.sup.(i), ZCR.sup.(i)), respectively, and c.sup.(i) moved forward to the next iteration.

[0161] Realization 7 is a modified version of the FPR2tm realization utilizing operation rescheduling, word decomposition, and CSA compression. Each iteration now consists of three compressions and one addition instead of three multiplications as was the case in realization 2. The first compression in line 5 compresses the 5-operand addition into 2 (temporary) integers (TS.sup.(i), TC.sup.(i)). Next, the required computation q.sup.(i)=(TS.sup.(i)+TC.sup.(i)modr)M′ modr is performed into two steps: a compression and an addition. In particular, a second compression in line 6 takes O(log m) units of delay to compress the 2m-operand addition into 2 integers (qS.sup.(i), qC.sup.(i). Notice that products (TS.sup.(i)modr)M′ and (TC.sup.(i)modr)M′, each produce m partial product terms that need to be added together. The m least significant bits of qS.sup.(i) and qC.sup.(i) are summed up in line 7, where the sum is generated by a logarithmic carry propagate adder (CPA), like the Kogge-Stone adder (KSA), requiring O(log m) levels of logic. Finally, the third compression in line 8 compresses the (2m+2)-operand addition into 2 integers (ZS.sup.(i), ZC.sup.(i)). Notice that multiplication with r=2.sup.m is simply done by left shifting the operand and that the products q.sup.(i)M and XY.sub.ir, each produce m partial product terms which must be summed together with TS.sup.(i) and TC.sup.(i).

TABLE-US-00007   Realization 7 Modified FPR2tm version 3 Input: X, Y ∈ [0, 2M), odd M < 2.sup.N, r = 2.sup.m, d =   [00021]$.Math.\frac{N+m+2}{m}.Math.,R=r^{d-1},{\mathrm{rr}}^{-1}-{\mathrm{MM}}^{\prime }=1$ Output: Z ∈ [0, 2M)  1: ZSM.sup.(−2) = 0, ZSM.sup.(−1) = 0, ZSR.sup.(−1) = 0  2: ZCM.sup.(−2) = 0, ZCM.sup.(−1) = 0, ZCR.sup.(−1) = 0  3: c.sup.(−1) = 0  4: for i = 0 to d − 1 do  5:  (TS.sup.(i), TC.sup.(i)) = Compress(ZSM.sup.(i−2)/r +    ZCM.sup.(i−2)/r + ZSR.sup.(i−1) + ZCR.sup.(i−1) + c.sup.(i−1))  6:  (qS.sup.(i), qC.sup.(i)) = Compress((TS.sup.(i) mod r)M′ +    (TC.sup.(i) mod r)M′)  7:  q.sup.(i) = (qS.sup.(i) + qC.sup.(i)) mod r  8:  (ZS.sup.(i), ZC.sup.(i)) = Compress(TS.sup.(i) + TC.sup.(i) + q.sup.(i)M + XY.sub.ir)  9:  c.sup.(i) = 1(ZC.sup.(i) mod r ≠ 0)  10:  (ZSM.sup.(i), ZSR.sup.(i)) = Decompose(ZS.sup.(i) >> m)  11:  (ZCM.sup.(i), ZCR.sup.(i)) = Decompose(ZC.sup.(i) >> m)  12: end for  13: Z = ZSM.sup.(d−2)/r + ZSM.sup.(d−1) + ZSR.sup.(d−1) +   ZCM.sup.(d−2)/r + ZCM.sup.(d−1) + ZCR.sup.(d−1) + c.sup.(d−1)  14: return Z

[0162] 1.1.4 Booth Coding

[0163] Because of the modular property to compute q.sup.(i)=(qS.sup.(i)+qC.sup.(i))modr, q.sup.(i) is not always identical to use qS.sup.(i)modr and qC.sup.(i)modr unless the sum of them is always less than r. Although it is possible to replace q.sup.(i) with qS.sup.(i)modr and qC.sup.(i)modr, the resulting (qS.sup.(i)modr)M and (qC.sup.(i)modr)M would cause double area compared with q.sup.(i)M. Instead, we choose to complete the modular addition q.sup.(i)=(qS.sup.(i)+qC.sup.(i))modr. Consequently, we can use radix-4 modified Booth coding to reduce the number of partial products for each multiplication performed in line 6 of realization 5.1.3 from 2m to m+2. Subsequently, we save m−2 CSAs and also reduce the delay. Modified Booth coding is not compatible with the carry-save form because it can achieve the correct result only after the final addition and ignore potential overflows. This is why we do not use Booth coding to improve the third compression in line 8 of realization 7.

[0164] 1.2 Radix-2.sup.m Scalable Montgomery Design

[0165] To extend the fixed-precision realization 7 to a scalable one (see realization 8 below), we need to iteratively compute w bits of intermediate results in realization 7 (see line 8). Moreover, we must find the maximum values of the intermediate results in order to derive e in terms of m. Equation (12) provides a way to compute the intermediate result Z.sup.(i) as shown next.

[00022]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{\left(i+1\right)}& =\mathrm{Mr}\underset{j=0}{\overset{i-1}{.Math.}}{q}^{\left(j+1\right)}{r}^j+\mathrm{Xr}\underset{j=0}{\overset{i}{.Math.}}{Y}_j{r}^j\\ & \le \mathrm{Mr}\left(r-1\right)\underset{j=0}{\overset{i-1}{.Math.}}{r}^j+\mathrm{Xr}\left(r-1\right)\underset{j=0}{\overset{i}{.Math.}}{r}^j\\ & =\mathrm{Mr}\left(r-1\right)\frac{r^i-1}{r-1}+\mathrm{Xr}\left(r-1\right)\frac{r^{i+1}-1}{r-1}\\ & <\left(M+\mathrm{Zr}\right)r^{i+1}\\ Z^{\left(i\right)}& <M+\mathrm{Xr}<\left(2r+1\right)<2^{N+m+2}\end{array}& \left(24\right)\end{array}$

[0166] Equation (24) shows that the maximum possible value of intermediate result Z.sup.(i) is always less than 2.sup.N+m+2 so that it can be presented in N+m+2 bits. Note that lines 10 and 11 of the realization 7 performs a division by r using a right shift by m bits. The maximum possible value of the intermediate result is the value just before the division, which can be presented in N+2m+2 bits. Therefore, minimum value of e can be set as

[00023]$e=.Math.\frac{N+2m+2}{w}.Math..$

Notice that that w≥2m, utilizing the triangle inequality

[00024]$e=.Math.\frac{N+2m+2}{w}.Math.\le .Math.\frac{N+2}{w}.Math.+1,$

we can derive a somewhat pessimistic lower bound on e which is

[00025]$e=.Math.\frac{N+2}{w}.Math.+1$

as was done for realization 4.

[0167] Partial results ZSR.sup.(i−1) and ZCR.sup.(i−1) in the i-th iteration of realization 7 may be explicitly represented as in equation (25), where the most m significant bits of ZSR.sub.j.sup.(i−1) and ZCR.sub.j.sup.(i−1) are 0.

ZSR.sup.(i−1)=Σ.sub.j=0.sup.e-1ZSR.sub.j.sup.(i−1)2.sup.wj

ZCR.sup.(i−1)=Σ.sub.j=0.sup.e-1ZCR.sub.j.sup.(i−1)2.sup.wj  (25)

[0168] Similarly, partial results ZSM.sup.(i−2)/r and ZCM.sup.(i−2)/r may explicitly be represented as in equation (26), where again the least w−m significant bits of ZSM.sub.j.sup.(i−2) and ZCM.sub.j.sup.(i−2) are 0. Note that ZSM.sup.(i−2) and ZCM.sup.(i−2) are multiples of r=2.sup.m because w−m≥m.

ZSM.sup.(i−2)/r=Σ.sub.j=0.sup.e-1(ZSM.sub.j.sup.(i−2)/r)2.sup.wj

ZCM.sup.(i−2)/r=Σ.sub.j=0.sup.e-1(ZCM.sub.j.sup.(i−2)/r)2.sup.wj  (26)

[0169] Consequently, line 5 of realization 7 may be rewritten as:

[00026]$\begin{array}{cc}\begin{array}{cc}\underset{j=0}{\overset{e-1}{.Math.}}({\mathrm{ZSM}}_j^{\left(i-2\right)}/r& +{\mathrm{ZCM}}_j^{\left(i-2\right)}/r+{\mathrm{ZSR}}_j^{\left(i-1\right)}\\ & +{\mathrm{ZCR}}_j^{\left(i-1\right)})2^{\mathrm{wj}}+c^{\left(i-1\right)}\\ & ={\mathrm{TS}}^{\left(i\right)}+{\mathrm{TC}}^{\left(i\right)}\end{array}& \left(27\right)\end{array}$

[0170] Moreover, because r=2.sup.m, we have:

[00027]$\begin{array}{cc}\begin{array}{cc}{q}^{\left(i\right)}& =\left(\left({\mathrm{TS}}^{\left(i\right)}\mathrm{mod}r\right)M^{\prime }+\left({\mathrm{TC}}^{\left(i\right)}\mathrm{mod}r\right)M^{\prime }\right)\mathrm{mod}r\\ & =({\mathrm{ZSM}}_0^{\left(i-2\right)}/r+{\mathrm{ZCM}}_0^{\left(i-2\right)}/2+{\mathrm{ZSR}}_0^{\left(i-1\right)}\\ & +{\mathrm{ZCR}}_0^{\left(i-1\right)}+c^{\left(i-1\right)})M^{\prime }\mathrm{mod}r\end{array}& \left(28\right)\end{array}$

[0171] Finally, X′Y.sub.i=Xr.Math.Y.sub.i and q.sup.(i)M can also be represented explicitly as follows:

X′Y.sub.i=Σ.sub.j=0.sup.e-1X′.sub.jY.sub.i2.sup.wj,q.sup.(i)M=q.sup.(i)M.sub.j2.sup.wj  (29)

[0172] The expression TS.sup.(i)+TC.sup.(i)+q.sup.(i)M+XY.sub.ir in line 8 of realization 7 can thus be written as:

[00028]$\begin{array}{cc}\begin{array}{cc}{\mathrm{TS}}^{\left(i\right)}& +{\mathrm{TC}}^{\left(i\right)}+q^{\left(i\right)}M+{\mathrm{XY}}_{i}r\\ & =\underset{j=0}{\overset{e-1}{.Math.}}({\mathrm{ZSM}}_j^{\left(i-2\right)}/r+{\mathrm{ZCM}}_j^{\left(i-2\right)}/r\\ & +{\mathrm{ZSR}}_j^{\left(i-1\right)}+{\mathrm{ZCR}}_j^{\left(i-1\right)}+X_j^{\prime }{Y}_i+q^{\left(i\right)}{M}_j)w^{\mathrm{wj}}\\ & +c^{\left(i-1\right)}\end{array}& \left(30\right)\end{array}$

[0173] In the context of the MWR2tm realization where N is variable, when Y.sub.i is provided in the i-th iteration, we need an inner loop to scan w bits of X′ and M in successive iterations. Consider any iteration i of the outer loop. In the 0-th inner loop iteration (j=0), let us redefine intermediate results (TS, TC) as the compression of ZSR.sub.0+ZCR.sub.0+ZSM′.sub.0/r+ZCM′.sub.0/r+c.Math.1(j==0), where ZSR.sub.0.sup.(i−1) and ZCR.sub.0.sup.(i−1) denote ZSR.sub.0.sup.(i) and ZCR.sub.0.sup.(i) in (current) iteration i whereas ZSM′.sub.0 and ZCM′.sub.0, denote ZSM.sub.0.sup.(i−1) and ZCM.sub.0.sup.(i−1) in (previous) iteration i−1. We can guarantee that only TS and TC need w−m+1 bits as shown in FIG. 7. From equation (28), TS and TC contain necessary information to allow calculation of q in the 0-th inner loop iteration.

[0174] Next, we compress TS+TC+X′.sub.0Y.sub.i+qM.sub.0 into intermediate results (OS, OC). Assume the bitwidths of OS and OC are w+x where x>0. The w least significant bits of OS and OC are actually ZS.sub.0.sup.(i) and ZC.sub.0.sup.(i) (parts of ZS.sup.(i) and ZC.sup.(i) in line 8 of realization 7), respectively. Consequently, we can compute c.sup.(i), ZSR.sub.0.sup.(i), and ZCR.sub.0.sup.(i). The most x significant bits of OS and OC will affect the computation of ZSR.sub.1.sup.(i) and ZCR.sub.1.sup.(i) and so on. These are named as FBS and FBC and used in the next inner loop iteration. Similarly, when we get to the 1-st inner loop iteration (j=1), we can update (TS, TC) as the compression of ZSR.sub.1+ZCR.sub.1+ZSM′.sub.1/r+ZCM′.sub.1/r+c.Math.1(j==0). Furthermore, we update (OS, OC) as the compression of TS+TC+X′.sub.1Y.sub.i+qM.sub.1+FBS+FBC. As before, the w least significant bits of OS and OC are actually ZS.sub.1.sup.(i) and ZC.sub.1.sup.(i) such that we can partition and assign them to ZSM.sub.0, ZCM.sub.0, ZSR.sub.1, and ZCR.sub.1. FBS and FBC are still updated as the x most significant bits of OS and OC. The procedure can proceed until all e inner loop iterations are completed.

[0175] One important question is how to set the bitwidths of FBS and FBC to guarantee that the bitwidths of OS and OC are large enough to avoid overflows. In another word, assume FBS and FBC each have x bits, the sum of OS and OC must be precisely representable with w+x bits. Equation (31) captures the constraints.

[00029]$\begin{array}{cc}\begin{array}{cc}(\left(2^w-1\right)\left(2^m-1\right)& +\left(2^{w-m+1}-1\right)\\ & +\left(2^x-1\right))\times 2<2^{w+x}\end{array}& \left(31\right)\end{array}$

[0176] One can easily prove the following result:

[00030]$\begin{array}{cc}\frac{2^2-1}{2^{w-1}-1}=\frac{2\left(2^{w-1}-1\right)+1}{2^{w-1}-1}<3\frac{2^{w-m+1}-2}{2^{w-1}-1}<1& \left(32\right)\end{array}$

[0177] Therefore, we can set x=m+2.

[00031]$\begin{array}{cc}\begin{array}{cc}\frac{\left(2^w-1\right)\left(2^m-1\right)+\left(2^{w-m+1}-2\right)}{2^{w-1}-1}& <3\left(2^m-1\right)+1\\ & <2^{m+2}\le 2^x\end{array}& \left(33\right)\end{array}$

[0178] Based on realization 7, we describe a radix-2.sup.m scalable Montgomery modular multiplication (MWR2tm) with an issue latency of L=1. Because the final result Z is in the range [0,2M), Z can also be represented in e words.

[0179] The last thing is to collect all carry-save form results together and compute the final Z=XYR.sup.−1modM. Once we have computed ZSM.sub.0, ZCM.sub.0, ZSR.sub.0, ZCR.sub.0, ZSM′.sub.0/r, ZCM′.sub.0/r, we are able to compress their sum into two (w+1)-bit integers (PS, PC). The w least significant bits PS[w−1: 0] and PC[w−1: 0] cooperate with c (working as the carry-in bit) to compute the last word Z.sub.0. The carry-out bit during the addition automatically works as carry-in in the next cycle. The two most significant bits are named as DO1 and DO2 to be added with ZSM.sub.1, ZCM.sub.1, ZSR.sub.1, ZCR.sub.1, ZSM′.sub.1/r, and ZCM′.sub.1/r. We thus compute Z.sub.1 and update DO1 and DO2. The procedure continues until we collect all e words of Z. We can guarantee it suffices to use two 1-bit DO1 and DO2 in (34). Detail of the compression is in the FIG. 9.

[00032]$\begin{array}{cc}\begin{array}{cc}(\left(2^m-1\right)\times 2^{w-m}& +\left(2^{w-m}-1\right)\\ & +\left(2^m-1\right)\times 2^{w-2m})\times 2+2\\ & \le 2\times \left(2^{w+1}-1\right)\end{array}& \left(34\right)\end{array}$

[0180] FIG. 2 shows an example of the i-th outer loop iteration when N=8, w=8, m=2, and

[00033]$e=.Math.\frac{N+2m+2}{w}.Math.=2.$

The modulus M has 8 bits so that M.sub.1 are 0. Because X E [0,2M), X′=Xr has N+1+m=11 bits and the least m=2 significant bits are 0.

TABLE-US-00008 Realization 8 Inventive scalable radix-2.sup.m Montgomery modular multiplication (MWR2tm) Input: X, Y ∈ [0, 2M), X′ = Xr, odd M < R = r.sup.kp−1,   [00034]$r=2^m,{\mathrm{rr}}^{-1}-{\mathrm{MM}}^{\prime }=1,w\ge 2m,e=.Math.\frac{N+2m+2}{w}.Math.,$   [00035]$k=.Math.\frac{N+m+2}{mp}.Math.,p=\mathrm{PE}\mathrm{count}$ Output: Z ∈ [0, 2M)  1: ZSM′ = 0, ZSM = 0, ZSR = 0  2: ZCM′ = 0, ZCM = 0, ZCR = 0, c = 0  3: for i = 0 to kp − 1 do {/ /outer loop}  4:  FBS = FBC = 0  5:  for j = 0 to e − 1 do {/ /inner loop}  6:   (TS, TC) = Compress(ZSR.sub.j + ZCR.sub.j + ZSM.sub.j′/r +     ZCM.sub.j′/r + c .Math. 1(j = = 0))  7:   if j = = 0 then  8:    (qS, qC) = Compress(TS mod r)M′ + (TC mod r)M′)  9:    q = (qS + qC) mod r 10:   end if 11:   (OS, OC) = Compress(TS + TC + X.sub.j′Y.sub.i + qM.sub.j + FBS +      FBC) 12:   c = 1(OC[m − 1:0] ≠ 0 and j = = 0) 13:   ZSM.sub.j−1 = ZSM.sub.j−1 14:   ZCM.sub.j−1 = ZCM.sub.j−1 15:   ZSM.sub.j−1 = OS[m − 1:0]2.sup.m−m 16:   ZCM.sub.j−1 = OC[m − 1:0]2.sup.m−m 17:   ZSR.sub.j = OS[w − 1:m] 18:   ZCR.sub.j = OC[w − 1:m] 19:   FBS = OS[w + m + 1:w] 20:   FBC = OC[w + m + 1:w] 21:  end for 22:  ZSM.sub.e−1 = ZSM.sub.−1 = 0 23:  ZCM.sub.e−1 = ZCM.sub.−1 = 0 24: end for 25: DO1 = DO2 = 0 26: Carry = c 27: for i = 0 to e − 2 do 28:  (PS, PC) = Compress(ZSM.sub.i + ZCM.sub.i + ZSR.sub.i +     ZCR.sub.i + ZSM.sub.i′/r + ZCM.sub.i′/r + DO1 + DO2) 29:  (Carry, Z.sub.i) = PS[w − 1:0] + PC[w − 1:0] + Carry 30:  DO1 = PS[w], DO2 = PC[w] 31: end for 32: return Z

[0181] 1.3. Scheduling and Performance Estimation

[0182] FIG. 2 shows the data dependency graph of realization 8. Node A denotes tasks of 0-th inner loop iteration for the MWR2tm algorithm. Node B denotes tasks of inner loop iteration when j≠0. Node C denotes the task in lines 25-31 of the MWR2tm algorithm. We can start the A task of PE i as soon as we finish the A task of PE i−1. The issue latency is thus L=1.

[0183] Each PE needs e cycles to execute one A task and (e−1) B tasks. Ideally, we need

[00036]$p=.Math.\frac{N+m+2}{m}.Math.\mathrm{PEs}.$

In the context of a scalable design, the bitwidth N of modulus M is variable such that we cannot know how many PEs are required in advance. As we mentioned earlier, after e cycles, a PE becomes free and may thus be reused. Assume p PEs are employed. Let k denote the number of rounds we use all p PEs, resulting in kp outer loop iterations in algorithm 5.2. From (14), it is easy to see that

[00037]$k=.Math.\frac{N+m+2}{\mathrm{mp}}.Math.$

guarantees that output Z will lie in [0,2M) as required.

[0184] FIG. 4 shows an example when N=6, w=4, m=2, and e=3. When we have p=3 PEs (p≥e) in FIG. 4(a), we need k=2 rounds. PE 1 finishes the computation about Y.sub.0 and becomes free when we need to issue Y.sub.3. Therefore, we need kp cycles to finish all A tasks. When we only have 2 PEs (p<e) in FIG. 4(b), we need k=3 rounds. When we want to issue Y.sub.2, PE 1 is still busy and we have to wait. Therefore, we need (k−1)e+p cycles to finish all A tasks. When all A tasks are done, we can start the C tasks and collect all carry-save form results, which needs e+1 cycles.

[0185] Based on the magnitude of p and e, the number of cycles required to perform Z=XYR.sup.−1modM (where inputs X and Y and output Z are in [0,2M)) by using the MWR2tm realization is as follows:

[00038]$\begin{array}{cc}\mathrm{cycle\_cnt}=(\begin{array}{cc}\mathrm{kp}+e+1& \mathrm{ife}\le p\\ \mathrm{ke}+p+1& \mathrm{otherwise}\end{array}\mathrm{where}r=2^m,p=\mathrm{PEcount},R=r^{\mathrm{kp}-1}=2^{m\left(\mathrm{kp}-1\right)}& \left(35\right)\\ e=.Math.\frac{N+2m+2}{w}.Math.,k=.Math.\frac{N+m+2}{\mathrm{mp}}.Math.& \left(36\right)\end{array}$

A simpler (upper bound) equation for the cycle count is:

cycle_cnt≤k max(e,p)+min(e,p)+1  (37)

where

n.sub.w=┌M/w┐

n.sub.m=┌N/m┐

e=n.sub.w+2

k=┌(n.sub.m+2)/p┐  (38)

[0186] Note that we use radix-2.sup.w for decomposing the multiplicand into e words of w bits each, and radix r=2.sup.m for decomposing the multiplier.

[0187] To start a required iteration of realization 7 on a new PE, we must collect enough information to compute the least m significant bits of TS.sup.(i) and TC.sup.(i) in line 5 so as to compute q.sup.(i). When w≥2m, after the first cycle, we finish the computation about the w−m least significant bits because we need to right shift by m bits. After the second cycle, we finish the computation about the 2w−m≥m least significant bits. The procedure goes on until all e inner loop iterations are done. So the issue latency is L=1.

[0188] Unfortunately, when m≤w<2m so that w−m<m, the MWR2tm realization cannot support an issue latency of L=1. Instead, we have 2w−m≥m and thus can only start computations on a new PE with an issue latency of 2 cycles. Generally speaking, the issue latency of realization 8 is L=┌(2m)/w┐. One may modify realization 8 and the corresponding data dependency graph to support various combination of w and m, some resulting in an issue latency of 1 cycle, others to an issue latency of 2 cycles or more.

[0189] Other optimization methods (such as increasing the cycle latency or increasing the circuit area as in [9, 10]) may be used to achieve L=1 even when m≤w<2m. In view of the above discussion, setting w≥2m provides the highest performance realization (i.e., realization 7) in terms of circuit area (hardware usage), cycle latency, and issue latency (L=1).

[0190] 1.4. Hardware Implementation

[0191] As we can observe, tasks A and B have many similarities and thus can be implemented in one PE by using a control signal CT as depicted in FIG. 5. In the A task (CT=1), the 5-to-2 compression handles variable c, the (2m+4)-to-2 compression masks inputs FBS and FBC to be 0 and forces the least m bits of outputs OS and OC to be 0, and finally q is calculated. In the B task (CT=0), the 5-to-2 compression masks c and thus forces it to be 0, the (2m+4)-to-2 compression accepts inputs FBS and FBC and generates OS and OC, and finally the stored value of q is used. Notice that ZSM.sub.i, ZSR.sub.i, etc. are represented by m bits, w−m bits, etc. instead of w bits, since the remaining bits are known to be zeros.

[0192] FIG. 7 shows the 5-to-2 compression of c.Math.1(j==0), ZSM′.sub.i/r, ZCM′.sub.i/r, ZSR.sub.i, and ZCR.sub.i by using two (w−m)-bit CSAs. Recall that the w−2m least significant bits of ZSM′.sub.i/r are 0.

[0193] Unlike A and B tasks, the C task needs only one special processing element (named PEc). FIG. 8 shows the implementation of the PEc. When CT=1, we force feedback signals DO1 and DO2 to 0 and set carry signal as c. When CT=0, we accept feedback signals DO1 and DO2 and set carry signal as the carry-out bit from the previous cycle.

[0194] Although there are 8 integers, we can compress them by using two w-bit CSAs as in FIG. 9. DZSR.sub.i stands for the delayed ZSR.sub.i (it is delayed by one clock cycle). The main delay of the C task is thus a w-bit addition, where we can use a KSA with a gate delay of log(w) to speed up the computation.

[0195] We show the block-level architecture of the proposed radix-2.sup.m scalable Montgomery modular multiplication in FIG. 6. The required ZSM′.sub.i and ZCM′.sub.i in the i-th outer loop iteration in realization 8 are actually ZSM.sub.i and ZCM.sub.i which are generated in the (i−2)-nd outer loop iteration. Similarly, ZSM′.sub.i and ZCM′.sub.i required in the PEc are ZSM.sub.i and ZCM.sub.i generated by the next to the last PE. To compute Z.sub.i, we need ZSM′.sub.i, ZCM′.sub.i, ZSM.sub.i, ZCM.sub.i, ZSR.sub.i, ZCR.sub.i, and c. However, they are not generated in the same cycle. More precisely, ZSM.sub.i and ZCM.sub.i are generated in the (i+1)-st inner loop iteration whereas ZSM′.sub.i, ZCM′.sub.i, ZSR.sub.i, ZCR.sub.i, and c are generated in the i-th inner loop iteration and need to be delayed by one clock cycle as shown in FIG. 8. When p<e as in FIG. 4(b), a first-in first-out queue with a depth of e−p slots is necessary to buffer the outputs.

[0196] 1.5. Hardware Emulation Results

[0197] 1.5.1 Analysis of Area and Time

[0198] The MWR2tm realization was coded in the Verilog hardware description language and implemented using the Xilinx Vivado Virtex 7 xc7v585tffg1157-3. Given a chip area constraint and the word size m of multiplier, there are many possible kernel configurations with the number p of PEs and the word size w of multiplicand for a designer-specified bitwidth N of the modulus M.

[0199] The number of cycles is a function of e and p as shown in equation (35). When e≤p, the cycle count is kp+e+1. A PE becomes free before we issue another word of the multiplier, meaning that we have instantiated too many PEs. The reduction of p can improve resource utilization until p=e. Note also that the change of p does not affect cycle count since kp is roughly a constant. When e>p, the cycle count is ke+p+1. A PE is still busy when we want to issue another word, so we have to wait for PEs to become available. Increasing p causes k to be reduced and thus lowers the cycle count until p becomes equal to e. Therefore, for a designer-specified bitwidth N of the modulus M, the optimum value of p is e.

[0200] Table 1 presents our implementations for different w and m combinations. (see, FIG. 27) As we discussed, the optimum p is

[00039]$e=.Math.\frac{N+2m+2}{w}.Math.,$

which is almost independent of m when w≥2m, and thus, decreases with the increase of w. Meanwhile, increasing w means that a PE is more complex, and hence, it will require more LUTs to do the required compressions and addition. Consequently, different implementations of the Montgomery MM with a fixed m have nearly the same area (in terms of the number of LUTs they need). The clock period of the kernel in FIG. 6. is bounded by the critical paths in both the PEs and the PEc. By increasing w, more computations are implemented as purely combinational logic, and thus the area decreases. However, when w becomes too large, the latency of the KSA addition in the PEc dominates the clock period such that the Montgomery MM time latency increases whereas the cycle latency is somewhat reduced. The placement and routing inside a PE also become more complex and require more area. Based on the product of area and time, the configurations (32,2), (64,4), and (128,8) for (w, m) achieve the best trade-off. When we run multivariate linear regression, we can estimate the area (LUT+FF) to scale as follows:

LUT_count=4.34wmp+6107  (39)

[0201] In the context of a scalable Montgomery MM design, N is a designer-specified variable, and therefore, we cannot optimize the architecture for a given N a priori. Instead, we presume an N value under constraints on the time latency and area. Choices of w, m, and p determine the latency and area for a presumed N as shown in table 1.

[0202] FIG. 10 shows the time latency of three scalable Montgomery modular multiplications with a presumed value of N=1,024. When the actual (designer-specified) N is less than or equal to 1,024, the difference of time latency is small as shown in FIG. 10(a). However, when the actual N is larger than 1,024 where e>p, a PE is still busy when we want to issue another word of the multiplier such that we have to wait. FIG. 10(b) shows the curve of time latency when N>1,024. When m increases, the slope decreases. Consequently, for actual N=16,384, the time latency of the configuration w=128, m=8, and p=9 is only 170.64 μs whereas the configuration w=32, m=2, and p=33 results in 332.2 μs time latency. FIG. 11 shows the corresponding throughput of the same configurations for the presumed N=1,024.

[0203] 1.5.2 Performance Comparison

[0204] Table 2 reports the performance of different Montgomery modular multiplications in terms of time and area. (see, FIG. 28). Notice that different radix (different m values) result in different products of area and time. Ideally, it would be fair to compare our design with other scalable designs under the same m value. However, to the best of the authors' knowledge, there is no high-radix scalable design, which does not use DSP's. Strictly speaking, we do not know the complexity of a DSP (used as a multiplier) in terms of an equivalent number of LUTs. Although we cannot compare area with DSP-based design [1, 15], the worst latency of our design when m=2 is still smaller than their latency. Meanwhile, many references [13, 16, 20] (regardless of whether they are scalable or not) focus on optimizations for a given radix (i.e., m is fixed). When m is small, the required multiplications can be explicitly optimized. When m is large, the multiplication cost becomes non-negligible, and many designs make use of the well-optimized DSP modules on FPGA. It is difficult or inefficient to extend these designs to support a parameterized m value.

[0205] References [4, 5, 21] provide parameterized but non-scalable designs. Recall that a scalable design optimized for a presumed value of N, for example N=1,024, can still support Montgomery modular multiplication for any N>1024, e.g., N=2048 and N=4096, whereas a non-scalable design cannot support cases when N>1024. Evidently, there are time and area overheads to convert a non-scalable design to a scalable one (if this conversion is possible at all), for example to perform decomposition of the intermediate results and employ complex connections among PEs. When m=2 and m=4, the area and time product of our proposed scalable design is 29.95% and 17.44% larger than the reference [21]. However, our design's overhead is constant since each PE has a fixed number of inputs and is only connected with at most two neighboring PEs. Recall that the critical delay of a PE is that of performing three compressions and one m-bit addition. Therefore, the clock period of a PE scales as O(log m). As a result, when m=8, our scalable design has a smaller product of area and time than the non-scalable designs in [4, 21].

[0206] 4. Inventive Design of a High-Performance, Fixed-Precision Montgomery Modular Multiplier Circuit

[0207] Feedforward Montgomery MM [19, 28] is a variant of Montgomery MM, which is able to compute q.sup.(i) and Z.sup.(i) in parallel. However, feedforward Montgomery MM can only guarantee that Z.sup.(d-1) in the last iteration falls in the range [0, 2.sup.m+1M). We cannot easily adjust Z back to the range [0, M) with a constant number of corrections. Note that the value of d can change for different variants of the Montgomery MM. In contrast, this thesis proposes an efficient fixed-precision Montgomery MM. For the sake of clarity, we first present a basic version of proposed Montgomery MM, in which we parallelize the computation of q.sup.(i) and Z.sup.(i) while guaranteeing that Z.sup.(d-1) lies in the range [0,2M). The basic version shows the correctness of proposed Montgomery MM. Next, we present an advanced version of the proposed Montgomery MM, in which multiplication and addition operations are replaced with encoding and compression operations. This advanced version significantly reduces the critical path delay while guaranteeing that Z.sup.(d-1) lies in the range (−M, 2M).

[0208] 2.1 Basic Version.

[0209] Realization 9 shows the basic version of proposed Montgomery MM. In this algorithm, q.sup.(i) and Z.sup.(i) are independent of each other and can thus be computed in parallel. Based on Bézout's identity, we can find r.sup.−1∈(0, M) and M″∈(0, r.sup.2) such that r.sup.2r.sup.−1−MM″=1.

TABLE-US-00009   Realization 9 Inventive fixed-precision radix-2.sup.m Montgomery modular multiplication: basic version Input: X, Y ∈ [0, M), odd M < 2.sup.N, r = 2.sup.m, d = ┌N/m┐ +  2, R = r.sup.┌N/m┐,  r.sup.2r.sup.−1 − M M″ = 1 Output: Z ∈ [0, M)  1: Z.sup.(−1) = 0, q.sup.(−1) = 0  2: for i = 0 to d − 1 do  3: g.sup.(i) = (Z.sup.(i−1) mod r.sup.2)M″ mod r.sup.2  4: q.sup.(i) = (g.sup.(i) − q.sup.(i−1))/r  5: Z.sup.(i) = (Z.sup.(i−1) + XY.sub.ir.sup.2 + q.sup.(i−1)M)/r  6: end for  7: Z = Z.sup.(d−1)  8: if Z > M then  9:  Z = Z − M 10: end if 11: return Z

[0210] Let us prove the correctness of realization 9 by mathematical induction. At the beginning, Z.sup.(−1)+q.sup.(−1)M=0 ≡.sub.r 0. Assume q.sup.(i−1)∈[0, r) and Z.sup.(i−1)+q.sup.(i−1)M ≡.sub.r 0. We would like to derive a q.sup.(i)∈[0, r) such that Z.sup.(i)+q.sup.(i)M ≡.sub.r 0. Note that this condition must be met in every iteration of the realization to ensure that the computational result is correct. To do this we first define: g.sup.(i)=Z.sup.(i−1)M″ modr.sup.2=(Z.sup.(i−1)modr.sup.2)M″ modr.sup.2 as in line 3 of realization 9. Next we show that Z.sup.(i−1)+g.sup.(i)M ≡.sub.r.sub.2 0 as follows:

[00040]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i-1\right)}+g^{\left(i\right)}M& =Z^{\left(i-1\right)}+\left(Z^{(i-1}{M}^{″}\mathrm{mod}{r}^2\right)M\\ & {\equiv }_{r^2}{Z}^{\left(i-1\right)}+Z^{\left(i-1\right)}{M}^{″}M\\ & =Z^{\left(i-1\right)}\left(1+{\mathrm{MM}}^{″}\right)\\ & =Z^{\left(i-1\right)}{r}^2{r}^{-1}\\ & {\equiv }_{r^2}0\end{array}& \left(40\right)\end{array}$

[0211] Furthermore, equation (40) implies the following:

Z.sup.(i−1)+g.sup.(i)M≡.sub.r0

Z.sup.(i−1)+(g.sup.(i)mod r)M≡.sub.r0  (41)

[0212] Because both q.sup.(i−1) and (g.sup.(i)modr) are valid choices in [0, r), due to uniqueness of q.sup.(i−1) up to a modulo on r, we conclude q.sup.(i−1)=g.sup.(i)modr. Therefore, g.sup.(i)−q.sup.(i−1) is a multiple of r i.e.,

g.sup.(i)−q.sup.(i−1)≡.sub.r0  (42)

[0213] In line 4 of realization 9, we have q.sup.(i)=(g.sup.(i)−q.sup.(i−1))/r. Because g.sup.(i) is 2m bits and q.sup.(i−1) is m bits, q.sup.(i) is also m bits. With this choice for q.sup.(i), and based on line 5 of realization 9, we can now prove that Z.sup.(i)+q.sup.(i)M ≡.sub.r 0. From equation (40), we know

[00041]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i-1\right)}+{\mathrm{XY}}_i{r}^2+g^{\left(i\right)}M& {\equiv }_{r^2}0\\ & \iff \\ \left(\frac{Z^{\left(i-1\right)}+{\mathrm{XY}}_i{r}^2+q^{\left(i–1\right)}M}{r}+\frac{g^{\left(i\right)}-q^{\left(i-1\right)}}{r}M\right)r& {\equiv }_{r^2}0\\ & \iff \\ Z^{\left(i\right)}+q^{\left(i\right)}M& {\equiv }_{r^2}0\end{array}& \left(43\right)\end{array}$

And the proof is complete.

[0214] Consequently, the three multiplications in realization 9 may be done in parallel. The critical path for computing Z.sup.(i) is thus reduced to one multiplication and two additions. We can also unfold the expression of Z.sup.(i) until Z.sup.(−1) as shown below:

Z.sup.(i)r.sup.i+1=Xr.sup.2Σ.sub.k=0.sup.iY.sub.kr.sup.k+MΣ.sub.k=0.sup.i=q.sup.(k−1)r.sup.k

Z.sup.(i)r.sup.i+1=Xr.sup.2Σ.sub.k=0.sup.iY.sub.kr.sup.k+Mr.sup.2Σ.sub.k=0.sup.i−2q.sup.(k+1)r.sup.k

Z.sup.(i)r.sup.i−1=XΣ.sub.k=0.sup.iY.sub.kr.sup.k+MΣ.sub.k=0.sup.i−2q.sup.(k+1)r.sup.k  (44)

Because Z.sup.(−1)=0, we have q.sup.(−1)=q.sup.(0)=0.

[0215] When i≥┌N/m┐−1, we have Σ.sub.k=0.sup.i Y.sub.kr.sup.k=Y. Because q.sup.(i)∈[0, r), we can estimate the upper bound of Z.sup.(i) as follows:

[00042]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i-1}& =X\underset{k=0}{\overset{i}{.Math.}}{Y}_k{r}^k+M\underset{k=0}{\overset{i-2}{.Math.}}{q}^{\left(k+1\right)}{r}^k\\ & \le \mathrm{XY}+M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k\\ & =\mathrm{XY}+M\left(r-1\right)\frac{r^{i-1}-1}{r-1}\\ & <\left(M+r^{i-1}\right)M\\ Z^{\left(i\right)}& <\left(1+\frac{M}{r^{i-1}}\right)M\end{array}& \left(45\right)\end{array}$

[0216] When (i−1)m≥N, we have M<2.sup.N≤2.sup.(i−1)m=r.sup.i−1 such that Z.sup.(i)<2M. Therefore, when we set d=┌N/m┐+2, we have Z.sup.(d-1)∈[0,2M). Compared with realization 2, realization 9 only needs two additional iterations.

[0217] 4.2 Advanced Version

[0218] Although realization 9 breaks the data dependency between q.sup.(i) and Z.sup.(i) and thus reduces the computation latency, multiplications and additions still hinder the development of a very high-performance Montgomery modular multiplication. Realization 10 shows an advanced version of the proposed Montgomery MM, which replaces all multiplications and additions in each iteration with encoding and compression operations. The result is an realization which can be implemented in hardware with much lower hardware area and computation latency than any and all prior art designs.

TABLE-US-00010   Realization 10 Inventive fixed-precision radix-2.sup.m Mont- gomery modular multiplication: advanced version Input: X, Y ∈ [0, M), odd M < 2.sup.N, r = 2.sup.m, d = ┌N/m┐ +  2, R = r.sup.┌N/m┐,  r.sup.2r.sup.−1 − M M″ = 1 Output: Z ∈ [0, M)  1: Z.sub.S.sup.(−1) = Z.sub.C.sup.(−1) = Z.sub.carry.sup.(−1) = q.sub.S.sup.(−1) = q.sub.C.sup.(−1) = q.sub.carry.sup.(−1) = 0  2: for i = 0 to d − 1 do  3: Z.sup.(i−1) = (Z.sub.S.sup.(i−1), = Z.sub.C.sup.(i−1), = Z.sub.carry.sup.(i−1))  4: Z.sub.L.sup.(i−1) = (Z.sub.S.sup.(i−1)[2m − 1 : 0], Z.sub.C.sup.(i−1)[2m − 1 :    0], Z.sub.carry.sup.(i−1))  5: Z.sub.L.sup.(i−1) = Encode(Z.sub.L.sup.(i−1))  6: q.sup.(i−1) = (q.sub.S.sup.(i−1), q.sub.C.sup.(i−1), q.sub.carry.sup.(i−1))  7: {tilde over (q)}.sup.(i−1) = Encode(q.sup.(i−1)), {circumflex over (q)}.sup.(i−1) = EncodeSN(q.sup.(i−1))  8: q.sub.S.sup.(i), q.sub.C.sup.(i) = Compress({tilde over (Z)}.sub.L.sup.(i−1) M″ − {circumflex over (q)}.sup.(i−1))  9: q.sub.carry.sup.(i) = q.sub.S.sup.(i)[m − 1] OR q.sub.C.sup.(i)[m − 1] 10: q.sub.S.sup.(i) = q.sub.S.sup.(i) >> m, q.sub.C.sup.(i) = q.sub.C.sup.(i) >> m 11: Y.sub.i = Y.sub.i − Y.sub.i[m − 1]r + Y.sub.i−1[m − 1] 12: (Z.sub.S.sup.(i), Z.sub.C.sup.(i)) = Compress(Z.sup.(i−1) + X{tilde over (Y)}.sub.ir.sup.2 + {circumflex over (q)}.sup.(i−1) M) 13: (Z.sub.S.sup.(i)[N + 3m] = (Z.sub.S.sup.(i)[N + 3m] XNOR Z.sub.C.sup.(i)[N + 3m] 14: Z.sub.C.sup.(i)[N + 3m] = 0 15: Z.sub.carry.sup.(i) = Z.sub.S.sup.(i)[m − 1] OR Z.sub.C.sup.(i)[m − 1] 16: Z.sub.S.sup.(i) = Z.sub.S.sup.(i) >> m, Z.sub.C.sup.(i) = Z.sub.C.sup.(i) >> m 17: end for 18: Z = Z.sub.S.sup.(d−1) + Z.sub.C.sup.(d−1) + Z.sub.carry.sup.(d−1) 19: if Z > M then 20: Z = Z − M 21: else if Z < 0 then 22: Z = Z + M 23: end if 24: return Z

[0219] In this algorithm, Z.sup.(i−1) is represented by three values: an (N+2m+1)-bit signed number Z.sub.S.sup.(i), an (N+2m+1)-bit signed number Z.sub.C.sup.(i−1), and a 1-bit unsigned value Z.sub.carry.sup.(i−1). Note that we do not explicitly perform the addition.

[00043]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i-1\right)}& =\left(Z_S^{\left(i-1\right)},Z_C^{\left(i-1\right)},Z_{\mathrm{carry}}^{\left(i-1\right)}\right)\\ & =Z_S^{\left(i-1\right)}+Z_C^{\left(i-1\right)}+Z_{\mathrm{carry}}^{\left(i-1\right)}\end{array}& \left(46\right)\end{array}$

[0220] The operation (Z.sup.(i−1)modr.sup.2) is simply replaced with Z.sub.L.sup.(i−1) as follows:

[00044]$\begin{array}{cc}\begin{array}{cc}{Z}_L^{\left(i-1\right)}& =\left(Z_S^{\left(i-1\right)}\left[2m-1:0\right],Z_C^{\left(i-1\right)}\left[2m-1:0\right],Z_{\mathrm{carry}}^{\left(i-1\right)}\right)\\ & =Z_S^{\left(i-1\right)}\left[2m-1:0\right]+Z_C^{\left(i-1\right)}\left[2m-1:0\right]+Z_{\mathrm{carry}}^{\left(i+1\right)}\\ & {\equiv }_{r^2}{Z}^{\left(i-1\right)}\mathrm{mod}{r}^2\end{array}& \left(47\right)\end{array}$

Notice that the difference between (Z.sup.(i−1)modr.sup.2) and Z.sub.L.sup.(i−1) is only 0 or r.sup.2. Similarly, q.sup.(i−1) is represented by an m-bit unsigned number q.sub.S.sup.(i−1), an m-bit unsigned number q.sub.C.sup.(i−1), and a 1-bit unsigned value q.sub.carry.sup.(i−1):

[00045]$\begin{array}{cc}\begin{array}{cc}{q}^{\left(i-1\right)}& =\left(q_S^{\left(i-1\right)},q_C^{\left(i-1\right)},q_{\mathrm{carry}}^{\left(i-1\right)}\right)\\ & =q_S^{\left(i-1\right)}+q_C^{\left(i-1\right)}+q_{\mathrm{carry}}^{\left(i-1\right)}\end{array}& \left(48\right)\end{array}$

[0221] Consider computing the expression Z=(A+B)*C, which shows up in each iteration of the Montgomery MM. Normally, we would need to first perform the full-size addition D=A+B followed by the multiplication Z=D*C (during which we can utilize the modified Booth coding to cut the number of generated partial product in half). This serial sequence of add and multiply operations increases the latency per iteration of algorithms 3.3 and 6.1. Notice that the hardware resource cost to compute the expression Z=A*C+B*C directly is costly so that is not an option. Instead, we propose a novel encoding technique (called Encode), which removes the necessity of performing the full-bitwidth addition of A and B when computing (A+B)*C, it does so by grouping and encoding every k bits of A and B and using these encoded k-bit groups to generate partial products of D*C. Although the Encode function is good for multiplication, the results of Encode are presented in a special format, which does not correspond to either signed number or unsigned number representations. Therefore, we propose an auxiliary version of Encode (call EncodeSN for Encode in Signed Numbers), which results are standard signed numbers. It will be shown that the sum of any values encoded by the EncodeSN function is equal to the sum of these values when they are encoded by the Encode function so that EncodeSN is used to perform addition and subtraction whereas Encode is used to do D*C.

[0222] We also point out that the Encode function when k=2 also results in removal of half of the partial products of D*C, similar to using a radix-4 modified Booth coding when doing D*C. In this thesis, we discuss and show the implementation of this encoding approach for the k=2 case. Extension to higher values of k is straight-forward.

[0223] 2.2.1 EncodeSN

[0224] Using a similar procedure as the one we did for realization 9, we determine e.sup.(i−1) so that Z.sup.(i−1)+q.sup.(i−1)M ≡.sub.r 0. Recall that q.sup.(i−1) is only unique up to a modulo on r as proved in (7). This observation motivates our encoding techniques, name Encode and EncodeSN. EncodeSN calculates (t+1)-bit outputs â and {circumflex over (b)} from t-bit inputs a and b. The encoding process consists of the following steps:

[0225] a) calculate a 3-bit intermediate result d as d[2: 0]=a[t−1: t−2]+b[t−1: t−2]+(a[t−3]ANDb[t−3]);

[0226] b) calculate â[t−4: 0]=a[t−4: 0] and {circumflex over (b)}[t−4: 0]=b[t−4: 0];

[0227] c) calculate â[t−3]=a[t−3] XORb[t−3]; â[t−2]=d[0]; â[t−1]=d[1]; â[t]=d[2];

[0228] d) calculate {circumflex over (b)}[t−1: t−3]=0; {circumflex over (b)}[t]=d[1].

The values of outputs a and b are defined as

v.sub.â=â[t]2.sup.t−â[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1â[i]2.sup.i

v.sub.{circumflex over (b)}={circumflex over (b)}[t]2.sup.t−{circumflex over (b)}[t−1]2.sup.t-1+Σ.sub.i=0.sup.t-1{circumflex over (b)}[i]2.sup.i  (49)

ensuring that v.sub.â+v.sub.{circumflex over (b)}=a+b.

[0229] We first perform EncodeSN(q.sub.S.sup.(i−1), q.sub.C.sup.(i−1)). Although the outputs are m+1 bits, we truncate outputs and assign the least m bits to {circumflex over (q)}.sub.S.sup.(i−1) and {circumflex over (q)}.sub.C.sup.(i−1). {circumflex over (q)}.sub.carry.sup.(i−1) is simply the q.sub.carry.sup.(i−1) itself. Because {circumflex over (q)}.sub.S[m]2.sup.m and {circumflex over (q)}.sub.C[m]2.sup.m are multiples of r=2.sup.m, the difference between {circumflex over (q)}.sup.(i−1)=({circumflex over (q)}.sub.S.sup.(i−1), {circumflex over (q)}.sub.C.sup.(i−1), {circumflex over (q)}.sub.carry.sup.(i−1)) and q.sup.(i−1) is a multiple or r so that

{circumflex over (q)}.sup.(i−1)≡.sub.rq.sup.(i−1)

Z.sup.(i−1)+{circumflex over (q)}.sup.(i−1)M≡.sub.r0  (50)

We use the notation {circumflex over (q)}.sup.(i−1)=EncodeSN(q.sup.(i−1)) to represent the said encoding process.

[0230] FIG. 12 shows the case of {circumflex over (q)}.sup.(i−1) when m=8, where the superscript (i−1) is omitted for brevity. The signs + and − stand for positive and negative weights respectively. As an example, q.sup.(i−1)=418 and {circumflex over (q)}.sup.(i−1)=−94. The difference q.sup.(i−1)−{circumflex over (q)}.sup.(i−1)=512=2*256=2*2.sup.8=2r.

[0231] 2.2.2 Encode

[0232] To explain the relationship between EncodeSN and Encode, we must carefully analyze the various steps of a 2-bit encoding as shown in FIG. 13. Considering 2-bit unsigned numbers a=2a.sub.1+a.sub.0 and b=2b.sub.1+b.sub.0, and 1-bit unsigned number c.sub.in. The goal is to compute c.sub.out, d, and e such that

a+b+c.sub.in=4c.sub.out−2d.sub.1+d.sub.0+4e  (51)

Note that d.sub.i=d[i] for i=0,1.

[0233] We define 2*c.sub.1+d.sub.0=a.sub.0+b.sub.0+c.sub.in for step (i) of FIG. 13. Table 3 presents the truth table for different a.sub.1, b.sub.1, and c.sub.1 so that a.sub.1+b.sub.1+c.sub.1=2d.sub.2+d.sub.1+2c.sub.out in step (ii). The overflow due to a.sub.1=b.sub.1 is captured in c.sub.out=a.sub.1ANDb.sub.1.

TABLE-US-00011 TABLE 3 Truth table for a.sub.1, b.sub.1, c.sub.1 a.sub.1 b.sub.1 c.sub.1 C.sub.out d.sub.2 d.sub.1 e 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 1 1

[0234] In step (iii), we split d.sub.1 as 2d.sub.1−d.sub.1. Notice that d.sub.2 and d.sub.1 cannot be 1 at the same time, therefore, we only need e=d.sub.2ORd.sub.1 to represent d.sub.2+d.sub.1 in step (iv). In conclusion, realization 11 shows the 2-bit encoding, which takes three inputs a, b, and c.sub.in and generates outputs e, d, and c.sub.out. The critical path delay is equal to that for a 2-bit adder. To avoid confusions, XOR and AND have the same precedence, which are higher than OR.

TABLE-US-00012   Realization 11 [c.sub.out, d, e] = Encode2bit(a, b, c.sub.in) Input: a[1 : 0], b[1 : 0], c.sub.in Output: C.sub.out, d[1 : 0], e  1: t = a.sub.0 AND b.sub.0 OR a.sub.0 AND c.sub.in OR b.sub.0 AND c.sub.in  2: c.sub.out = a.sub.1 AND b.sub.1  3: d.sub.0 = a.sub.0 XOR b.sub.0 XOR c.sub.in  4: d.sub.1 = a.sub.1 XOR b.sub.1 XOR t  5: e = a.sub.1 XOR b.sub.1 OR t

[0235] Taking a second look at {circumflex over (q)}.sup.(i−1)=EncodeSN(q.sup.(i−1)), we actually do 2-bit encoding for the leading 2 bits of q.sub.S.sup.(i−1) and q.sub.C.sup.(i−1) with c.sub.in=q.sub.S.sup.(i−1)[m−3]ANDq.sub.C.sup.(i−1)[m−3] and ignore the outputs c.sub.out and e. Note that q.sub.S.sup.(i−1)[m−3] and q.sub.C.sup.(i−1)[m−3] are adjusted accordingly. Instead of only encoding the leading 2 bits of q.sub.S.sup.(i−1) and q.sub.C.sup.(i−1), we can encode every 2 bits.

[0236] Realization 12 calculates (t+1)-bit outputs ã and {tilde over (b)} for two t-bit inputs a and b and a 1-bit input c. Without loss of generality, we assume the bitwidth t for inputs a and b is even. Otherwise, we can pad a 0 to the left of a and b. The output c.sub.out in a 2-bit encoding is used as the input c.sub.in for the next 2-bit encoding. For example, the c.sub.out from Encode2 bit(a[t−3: t−4], b[t−3: t−4], c.sub.in) serves as the c.sub.in for Encode2 bit(a[t−1: t−2], b[t−1: t−2], c.sub.in).

TABLE-US-00013   Realization 12 [ã, {tilde over (b)}] = Encode (a, b, c) Input: t-bit unsigned a and b, 1-bit unsigned c Output: (t + 1)-bit ã and {tilde over (b)}  1: ã = {tilde over (b)} = 0, c.sub.out.sup.(−1) = c  2: for i = 0 to t/ 2 − 1 do  3:  [c.sub.out.sup.(i), e.sup.(i), d.sup.(i)] = Encode2bit(a[2i+1:2i], b[2i+1:2i], c.sub.out.sup.(i−1),  4:  ã[2i + 1 : 2i] = d.sup.(i)  5:  {tilde over (b)}[2i + 2] = e.sup.(i)  6: end for  7: ã[t] = c.sub.out.sup.(t/2−1)

[0237] Recall that the sum of inputs is equal to the sum of outputs for a 2-bit encoding as shown in (51). The goal of the Encode procedure is to represent the sum a+b+c in a different format. The values of ã and {tilde over (b)} are defined as

v.sub.ã=Σ.sub.i=0.sup.t/2ã[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1ã[2i+1]2.sup.2i+1

v.sub.{tilde over (b)}=Σ.sub.i=0.sup.t/2{tilde over (b)}[2i]2.sup.2i−Σ.sub.i=0.sup.t/2-1{tilde over (b)}[2i+1]2.sup.2i+1  (52)

ensuring that v.sub.ã+v.sub.{tilde over (b)}=a+b+c.

[0238] If we also apply (â, {circumflex over (b)})=EncodeSN(a, b), we must have

v.sub.â+v.sub.{circumflex over (b)}+c=a+b+c=v.sub.ã+v.sub.{tilde over (b)}

â[t]+{circumflex over (b)}[t]=ã[t]+{tilde over (b)}[t]  (53)

[0239] We can perform Encode(q.sub.S.sup.(i−1), q.sub.C.sup.(i−1), q.sub.carry.sup.(i−1). Similar to the computation of {circumflex over (q)}.sup.(i−1), we can truncate outputs and assign the least m bits to {tilde over (q)}.sub.S.sup.(i−1) and {tilde over (q)}.sub.C.sup.(i−1). Because of equation (53), we have:

{tilde over (q)}.sup.(i−1)={circumflex over (q)}.sup.(i−1)

Z.sup.(i−1)+{tilde over (q)}.sup.(i−1)M≡.sub.r0  (54)

We use the notation {tilde over (q)}.sup.(i−1)=Encode(q.sup.(i−1)) to represent the said encoding process.

[0240] Although realization 12 is presented by a for loop, all 2-bit encodings can be preformed in parallel. FIG. 14 shows the example when m=8. In step (ii), we group 2 bits and compute c.sub.out for each group. In step (iii), we perform 2-bit encoding and generate outputs e and d for each group. c.sub.out is already computed and used in step (ii). In step (iv), we combine results into two numbers. Output e when encoding the leading 2 bits is ignored. In step (v), we fill empty slots with 0. Notice that we get all information in step (iii). Steps (iv) and (v) are only shown to explain the computation to the reader. The critical path delay to perform Encode is roughly equal to that of a 2-bit adder.

[0241] An important observation is that we can group 2-bit parts of {tilde over (q)}.sup.(i−1) again. As shown in step (v) of FIG. 14, some bits are constant 0. Their value can be treated as (−2)*4.sup.3+2*4.sup.2+1*4.sup.1+(−2)*4.sup.0=−94. The value range for a group is [−2,2]. Like radix-4 modified Booth coding, we can use a group to generate a partial product directly. When we compute {tilde over (q)}.sup.(i−1)M, we only have m/2 partial products. There is no need to do an m-bit addition for q.sub.S.sup.(i−1)+q.sub.C.sup.(i−1)+q.sub.carry.sup.(i−1) any more. Since the range of a group is [−2,2], the range of m-bit {tilde over (q)}.sup.(i) is

[00046]$\left[-\frac{2}{3}\left(r-1\right),\frac{2}{3}\left(r-1\right)\right]$

as shown below:

[00047]$\begin{array}{cc}\begin{array}{cc}{\tilde{q}}^{\left(i\right)}& \le \underset{k=0}{\overset{m/2-1}{.Math.}}2*4^k=2*\frac{4^{m/2}-1}{4-1}\\ & =\frac{2}{3}\left(2^m-1\right)=\frac{2}{3}\left(r-1\right)\\ {\tilde{q}}^{\left(i\right)}& \ge \underset{k=0}{\overset{m/2-1}{.Math.}}\left(-2\right)*4^k=-\frac{2}{3}\left(r-1\right)\end{array}& \left(55\right)\end{array}$

[0242] 2.2.3 Computation of q.sup.(i)

[0243] Recall the computation of g.sup.(i)=(Z.sup.(i−1)modr.sup.2)M″ modr.sup.2 in realization 9, resulting in Z.sup.(i−1)+g.sup.(i) M ≡.sub.r.sub.2 0, that is

Z.sup.(i−1)+((Z.sup.(i−1)mod r.sup.2)M″ mod r.sup.2)M≡.sub.r.sub.20  (56)

[0244] If we add/subtract any multiples of r.sup.2 to/from (Z.sup.(i−1)modr.sup.2), the above equation will still hold. In other words, it is safe to replace (Z.sup.(i−1)modr.sup.2) with Z.sub.L.sup.(i−1) or {tilde over (Z)}.sub.L.sup.(i−1)=Encode(Z.sub.L.sup.(i−1)), because the difference between any two of (Z.sup.(i−1)modr.sup.2), Z.sub.L.sup.(i−1), and {tilde over (Z)}.sub.L.sup.(i−1) is a multiple of r.sup.2. The benefit is that we will only have m partial products if we compute {tilde over (Z)}.sub.L.sup.(i−1)M″. We thus have:

Z.sup.(i−1)+({tilde over (Z)}.sub.L.sup.(i−1)M″ mod r.sup.2)M≡.sub.r.sub.20  (57)

[0245] Equation (57) implies:

Z.sup.(i−1)+({tilde over (Z)}.sub.L.sup.(i−1)M″ mod r)M≡.sub.r.sub.20  (58)

[0246] Considering equation (50) and the uniqueness of q.sup.(i−1) up to a modulo on r, we have

{tilde over (Z)}.sub.L.sup.(i−1)M″ mod r−{circumflex over (q)}.sup.(i−1)≡.sub.r0  (59)

[0247] Following equation (43) which was related to realization 9, the obtained q.sup.(i) for realization 10 should meet the following requirement:

[00048]$\begin{array}{cc}{q}^{\left(i\right)}{\equiv }_r\frac{{\tilde{Z}}_L^{\left(i-1\right)}{M}^{″}-{\hat{q}}^{\left(i-1\right)}}{r}& \left(60\right)\end{array}$

[0248] FIG. 15 shows compression of {tilde over (Z)}.sub.L.sup.(i−1) M″−{circumflex over (q)}.sup.(i−1) for the least significant 2m bits. In step (i), we use CSA to compress m+3 numbers into two unsigned numbers q.sub.S.sup.(i) and q.sub.C.sup.(i). Notice that each partial product has a tail bit. The aforesaid m+3 numbers consist of three parts: m numbers from {tilde over (Z)}.sub.L.sup.(i−1)M″, 2 numbers from {circumflex over (q)}.sub.S.sup.(i−1) and {circumflex over (q)}.sub.C.sup.(i−1), and 1 number constructed by collecting the tail bits and {circumflex over (q)}.sub.carry.sup.(i−1). We then use a balanced ternary tree arrangement of CSAs to perform the compression (q.sub.S.sup.(i), q.sub.C.sup.(i))=Compress({tilde over (Z)}.sub.L.sup.(i−1)M″−{circumflex over (q)}.sup.(i−1)) with O(log m) number of full adder cell delays. Here, we do the fixed-bitwidth compression and collect the least significant 2m bits of the two numbers after compression because any overflow is a multiple of r.sup.2.

[0249] Because of equation (59), the sum of the least significant m bits can only be 0 or r. When q.sub.S.sup.(i)[m−1]=1 or q.sub.C.sup.(i)[m−1]=1, the following equality holds: q.sub.S.sup.(i)[m−1: 0]+q.sub.C.sup.(i)[m−1: 0]=r. On the other hand, when q.sub.S.sup.(i)[m−1]=q.sub.C.sup.(i)[m−1]=0, we have q.sub.S.sup.(i)[m−1: 0]+q.sub.C.sup.(i)[m−1: 0]=0. Therefore, we may define q.sub.carry.sup.(i) as follows:

q.sub.carry.sup.(i)=q.sub.S.sup.(i)[m−1]ORq.sub.C.sup.(i)[m−1]

q.sub.carry.sup.(i)r=q.sub.S.sup.(i)[m−1: 0]+q.sub.C.sup.(i)[m−1:0]  (61)

[0250] In step (ii), the computation of ({tilde over (Z)}.sub.L.sup.(i−1)M″−{circumflex over (q)}.sup.(i−1))/r is reduced to a right shift by m bits:

q.sub.carry.sup.(i)=q.sub.S.sup.(i)[m−1]ORq.sub.C.sup.(i)[m−1]

q.sub.S.sup.(i)=q.sub.S.sup.(i)>>m

q.sub.C.sup.(i)=q.sub.C.sup.(i)>>m  (62)

[0251] Note that the resulting q.sup.(i)=(q.sub.S.sup.(i), q.sub.C.sup.(i), q.sub.carry.sup.(i)) is valid since it meets equation (60). Consequently, the computation of q.sup.(i) relies on encoding and compression operations, rather then the more expensive multiplication and addition operations.

[0252] 2.2.4 Error Analysis

[0253] Before doing the error analysis for Z.sup.(i), let us briefly discuss the optimization to compute XY.sub.i based on the modified Booth coding. Instead of computing XY.sub.i, we scan Y.sub.i and Y.sub.i−1[m−1] and encode them as {tilde over (Y)}.sub.i, that is,

[00049]$\begin{array}{cc}\begin{array}{cc}{\tilde{Y}}_i& =Y_i-Y_i\left[m-1\right]r+Y_{i-1}\left[m-1\right]\\ & =\underset{k=0}{\overset{m/2-1}{.Math.}}(-2Y\left[2k+1+\mathrm{im}\right]\\ & +Y\left[2k+\mathrm{im}\right]+Y\left[2k-1+\mathrm{im}\right]k)4^k\end{array}& \left(63\right)\end{array}$

Note that Y.sub.−1=0.

[0254] Following the radix-4 modified Booth coding, we can further divide {tilde over (Y)}.sub.i into m/2 groups if we group every 2 bits. In case m is an odd number, we can sign-extend {tilde over (Y)}.sub.i by 1 bit and generate ┌m/2┐ groups. Alternatively, we can directly apply radix-2.sup.m modified Booth coding to {tilde over (Y)}.sub.i. Because the range of −2Y[2k+1+im]+Y[2k+im]+Y[2k−1+im] is [−2,2], we can use it to generate a partial product. Consequently, the product of X{tilde over (Y)}.sub.i has m/2 partial products, whereas XY.sub.i has m/2+1 partial products. Moreover, the range of {tilde over (Y)}.sub.i falls in [−r/2, r/2] as shown next:

[00050]$\begin{array}{cc}\begin{array}{cc}{Y}_i& \in \left[0,2^m-1\right]\\ Y_i-Y_i\left[m-1\right]r& \in \left[-2^{m-1},2^{m-1}-1\right]\\ {\tilde{Y}}_i& =Y_i-Y_i\left[m-1\right]r+Y_{i-1}\left[m-1\right]\\ & \in \left[-2^{m-1},2^{m-1}\right]=\left[-\frac{r}{2},\frac{r}{2}\right]\end{array}& \left(64\right)\end{array}$

[0255] We can further compute the range for Σ.sub.k=0.sup.i {tilde over (Y)}.sub.k as follows:

[00051]$\begin{array}{cc}\begin{array}{cc}\underset{k=0}{\overset{i}{.Math.}}{\tilde{Y}}_k{r}^k& =\underset{k=0}{\overset{i}{.Math.}}{Y}_k{r}^k-Y\left[\left(i+1\right)m-1\right]r\\ & \in [-2^{\left(i+1\right)m-1},2^{\left(i+1\right)m-1})=[-\frac{r^{i+1}}{2},\frac{r^{i+1}}{2})\end{array}& \left(65\right)\end{array}$

[0256] When (i+1)m−1≥N, we have Y[(i+1)m−1]=0 so that

Y=Σ.sub.k=0.sup.┌N/m┐−1Y.sub.kr.sup.k=Σ.sub.k=0.sup.┌(N+1)/m┐−1{tilde over (Y)}.sub.kr.sup.k  (66)

[0257] Since Z.sup.(i)=(Z.sup.(i−1)+X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M)/r, we can unfold the expression until Z.sup.(−1)=0 as shown below:

Z.sup.(i)r.sup.i+1=Xr.sup.2Σ.sub.k=0.sup.i{tilde over (Y)}.sub.kr.sup.k+MΣ.sub.k=0.sup.i{tilde over (q)}.sup.(k−1)r.sup.k

Z.sup.(i)r.sup.i+1=Xr.sup.2Σ.sub.k=0.sup.i{tilde over (Y)}.sub.kr.sup.k+Mr.sup.2Σ.sub.k=0.sup.i−2{tilde over (q)}.sup.(k−1)r.sup.k

Z.sup.(i)r.sup.i−1=XΣ.sub.k=0.sup.i{tilde over (Y)}.sub.kr.sup.k+MΣ.sub.k=0.sup.i−2{tilde over (q)}.sup.(k−1)r.sup.k  (67)

Note that because Z.sup.(−1)=0, we have {tilde over (q)}.sup.(0)={tilde over (q)}.sup.(−1)=0.

[0258] When i≥┌(N+1)/m┐−1, the following equality holds:

[00052]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{\left(i+1\right)}& =X\underset{k=0}{\overset{i}{.Math.}}{\tilde{Y}}_k{r}^k+M\underset{k=0}{\overset{i-2}{.Math.}}{\tilde{q}}^{\left(k+1\right)}{r}^k\\ & =\mathrm{XY}+M\underset{k=0}{\overset{i-2}{.Math.}}{\tilde{q}}^{\left(k+1\right)}{r}^k\end{array}& \left(68\right)\end{array}$

[0259] We can derive upper and lower bounds for Z.sup.(i) as follows:

[00053]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i-1}& <M^2+\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k\\ & <M^2+\frac{2}{3}M\left(r-1\right)\frac{r^{i-1}-1}{r-1}\\ & <\left(M+\frac{2}{3}{r}^{i-1}\right)M\\ Z^{\left(i\right)}& <\left(\frac{2}{3}+\frac{M}{r^{i-1}}\right)M\\ Z^{\left(i\right)}{r}^{i-1}& \ge 0-\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k>\left(-\frac{2}{3}{r}^{i-1}\right)M\\ Z^{\left(i\right)}& >-\frac{2}{3}M>-M\end{array}& \left(69\right)\end{array}$

[0260] When meeting the condition M/r.sup.i−1≤4/3, we have −M<Z.sup.(i)<2M. Equation (70) given below simplifies this condition. Because log.sub.2.sup.3M<N+2, this condition is met when N≤(i−1)m. Therefore, when we set d=┌N/m┐+2, we have Z.sup.(d-1)∈(−M, 2M). We only need one correction, either addition or subtraction, to adjust Z back to [0, M).

M/r.sup.i−1≤4/3⇔3M≤2.sup.(i−1)m+2

⇔ log.sub.2.sup.3M≤(i−1)m+2  (70)

[0261] We can also compute the maximum size of any intermediate result Z.sup.(i) as follows. Recall that

[00054]$.Math.\underset{k=0}{\overset{i}{.Math.}}{\tilde{Y}}_k{r}^k.Math.\le \frac{r^{i+1}}{2}\mathrm{and}.Math.{\tilde{q}}^{\left(k+1\right)}.Math.\le \frac{2}{3}\left(r-1\right).$

[00055]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i-1}& =X\underset{k=0}{\overset{i}{.Math.}}{\tilde{Y}}_k{r}^k+M\underset{k=0}{\overset{i-2}{.Math.}}{\tilde{q}}^{\left(k+1\right)}{r}^k\\ .Math.Z^{\left(i\right)}{r}^{i-1}.Math.& <M\frac{r^{i+1}}{2}+\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k\\ & <M\left(\frac{r^{i+1}}{2}+\frac{2}{3}{r}^{i-1}\right)\\ .Math.Z^{\left(i\right)}.Math.& <M\left(\frac{r^2}{2}+\frac{2}{3}\right)<2^{N+2m}\end{array}& \left(71\right)\end{array}$

[0262] In other words, independent of the iteration count i, any Z.sup.(i) can be represented by an (N+2m+1)-bit signed number.

[0263] 2.2.5 Computation of Z.sup.(i)

[0264] The last thing to do is to efficiently compute Z.sup.(i)=(Z.sup.(i−1)+X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M)/r. At this time, it is not safe to add or subtract a multiple of r. Our proposed encoding and modified Booth coding save half of the partial products and reduce the hardware area. After compression, the partial products are compressed into two signed numbers. We can do an addition (while ignoring any overflows) to get the correct result. FIG. 16 shows an example to compute 8-bit signed multiplication for C=AB with radix-4 modified Booth coding. For A=108 and B=125, the correct product C is 13,500. Once we get all 4 partial products, we compress them into two 16-bit signed numbers CS and CC. Although CS+CC=−52,036≠13,500, we can perform the 16-bit addition while ignoring the overflow bit, thereby obtaining the correct result.

[0265] The said addition of the two signed numbers seems necessary. We show next that in fact this costly add operation can be avoided and the computation of Z.sup.(i) can be accomplished by using only encoding and compression operations.

[0266] As we discussed in equation (71), Z.sup.(i) is an (N+2m+1)-bit signed number. We want to accurately represent Z.sup.(i) by a triplet: an (N+2m+2)-bit signed number Z.sub.S.sup.(i), an (N+2m+2)-bit signed number Z.sub.C.sup.(i), and a 1-bit unsigned value Z.sub.carry.sup.(i). FIG. 15 shows our general data model, where the leading 2 bits of Z.sub.S are same and the leading 2 bits of Z.sub.C are 0. Because the resulting Z is an (N+2m+1)-bit signed number, Z[N+2m+1] must be the sign extension.

[0267] We define the carry from the addition for the least significant (N+2m) bits as C.sub.in. Table 4 shows all possible combinations of S.sub.1 and C.sub.in. Notice that it is impossible to have S.sub.1=0 and C.sub.in=1 because the resulting Z becomes larger than 2.sup.N+2m, which would violate the fact that Z is a (N+2m+1)-bit signed number. For the remaining three cases, Z.sub.S.sup.(i)+Z.sub.C.sup.(i)+Z.sub.carry.sup.(i) can never have any overflows, therefore, the sum Z.sup.(i) can be correctly presented.

TABLE-US-00014 TABLE 4 Truth table for the proposed data mode S.sub.1 C.sub.in S.sub.2 0 0 0 0 1 N.A. 1 0 1 1 1 0

[0268] We again prove the result by using mathematical induction. The base case is Z.sup.(−1)=Z.sub.S.sup.(−1)+Z.sub.C.sup.(−1)+Z.sub.carry.sup.(−1)=0. Assume Z.sup.(i−1)=(Z.sub.S.sup.(i−1), Z.sub.C.sup.(i−1), Z.sub.carry.sup.(i−1)) fits in the data model of FIG. 15, if we show that Z.sup.(i)=(Z.sub.S.sup.(i), Z.sub.C.sup.(i), Z.sub.carry.sup.(i)) also fits in the data model, then we will have proven that the sum Z.sup.(i) can be correctly presented.

[0269] FIG. 18 shows the computation of Z.sup.(i). Both {tilde over (q)}.sup.(i−1)M and X{tilde over (Y)}.sub.ir.sup.2 generate m/2 partial products. Z.sup.(i−1) is represented by Z.sub.S.sup.(i−1), Z.sub.C.sup.(i−1), and Z.sub.carry.sup.(i−1). Because Z.sup.(i) is an (N+2m+1)-bit signed number, Z.sup.(i−1)+X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M=Z.sup.(i)r is an (N+3m+1)-bit signed number, which is also a multiple of r. To sum all partial products together, the first thing to do is to sign extend the numbers so that all of them have same bitwidth. Here, we deliberately extend them into N+3m+2 bits in step (i) of FIG. 18. For sake of brevity, all signs are labelled as S although different numbers could have different sign values.

[0270] The sign bits in a number can be converted into 1's followed by a S in step (ii). Any overflows can be ignored because Z.sup.(i)r only has (N+3m+1) bits. S is the Boolean inversion of S. We further merge all constant 1's into a number called prefix in step (iii) after ignoring any overflows. Because the prefix is a constant number which is only dependent on m, the real implementation can skip steps (i) and (ii), and start at step (iii). When m≥4, we can prove that the maximum value for dashed polygon in step (iii) is less than 2.sup.N+3m+1 as shown below:

[00056]$\begin{array}{cc}\begin{array}{cc}\left(\underset{k=0}{\overset{m/2-1}{.Math.}}\left(2^N-1\right)4^k\right)& +\left(\underset{k=0}{\overset{m/2-1}{.Math.}}\left(2^N-1\right)4^k\right)2^{2m}\\ & +2\left(2^{N+2m+1}-1\right)+1\\ & +3*2^{N+3m-3}\\ & <2^{N+3m+1}\end{array}& \left(72\right)\end{array}$

[0271] Since the dashed polygon is less than 2.sup.N+3m+1 the compression of the m+3 numbers will result in two (N+3m+1)-bit unsigned numbers Z.sub.S.sup.(i) and Z.sub.C.sup.(i) in step (iv) regardless of the compression strategy. Note that Z.sub.S[N+3m] and Z.sub.C[N+3m] cannot be 1 at the same time; otherwise Z.sub.S.sup.(i)+Z.sub.C.sup.(i) will be larger than 2.sup.N+3m+1. As a result, the sum of Z.sub.S[N+3m], Z.sub.C[N+3m], and the leading 2 bits of the prefix will be a 2-bit number with the same value, which is Z.sub.S[N+3m]XNORZ.sub.C[N+3m]. Since Z.sub.S[N+3m] is always the same as Z.sub.S[N+3m+1], we can hide Z.sub.S[N+3m+1] and Z.sub.C[N+3m+1] in a hardware implementation.

[0272] Because Z.sup.(i−1)+X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M ≡.sub.r 0, in step (v), the operation (Z.sup.(i−1)+X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M)/r can be simplified as shown below:

Z.sub.carry.sup.(i)=Z.sub.S.sup.(i)[m−1]ORZ.sub.C.sup.(i)[m−1]

Z.sub.S.sup.(i)=Z.sub.S.sup.(i)>>m

Z.sub.C.sup.(i)=Z.sub.C.sup.(i)>>m  (73)

Because Z.sup.(i)=(Z.sub.S.sup.(i), Z.sub.C.sup.(i), Z.sub.carry.sup.(i)) fits the data model in FIG. 17, we thus correctly present Z.sup.(i) without doing an addition.

[0273] When m<4, we can modify the data model of FIG. 17 to have N+2m+3 bits, sign extend all numbers into (N+3m+3) bits in step (i), and prove the dashed polygon is less than 2.sup.N+3m+2 in step (iii). The remaining proofs are similar to what we did above and are thus omitted here for brevity.

[0274] 2.3 Hardware Implementation

[0275] FIG. 19 shows the block-level diagram for the hardware implementation of the proposed Montgomery modular multiplier. With the help of Encode, EncodeSN, and compression, the critical paths to update (q.sub.S, q.sub.C, q.sub.carry) and (Z.sub.S, Z.sub.C, Z.sub.carry) correspond to those for doing a 2-bit addition and compression of m+3 numbers.

[0276] The critical path of the proposed Montgomery MM thus lies in the addition module for the final summation and correction step. Considering the trade-off between time and area, we use a high performance logarithmic Brent-Kung adder (BKA) [2] and specify a 3-cycle timing constraint. Note that we need to perform one final summation and do at most one correction. We only need to use BKA twice in 6 consecutive cycles, which justifies the 3-cycle timing constraint. The control signal CT is used to control the data flow of BKA. When CT=0, we compute Z.sub.S+Z.sub.C+Z.sub.carry and store it in Z. When CT=1, we check the sign of Z. If Z<0, we compute Z+M. If Z≥0, we compute Z−M. If the computation result is negative, we do not need any correction and simply choose the original Z. Otherwise, the result, which is positive, is stored into Z. In conclusion, the total clock cycle count to do the Montgomery MM is only

CycleCount=u+6  (74)

where u=┌N/m┐+2 is the number of iterations.

[0277] 2.4 Complexity Analysis

[0278] Table 5 shows complexity analysis for different algorithms in terms of area and time. The iteration count, which remains the same for all algorithms, is equal to O(N/m). Assume we use a textbook multiplier to perform an N×m multiplication with area and time complexities of O(Nm). For algorithms 3.3 and 6.1, the critical path in each iteration is bounded by the multiplications such that the area and time complexity per iteration of the realization are O(Nm). Meanwhile, the clock period (latency per iteration) for realization 10 is reduced a lot due to replacement of additions and multiplications with compression and encoding operations. More precisely, since encoding only takes a constant delay and compression has O(log m) time complexity, the clock period is O(log m) time. Although encoding technique and modified Booth coding reduce the number of partial products by a factor of two, the area complexity remains O(Nm). As a result, the area-time product complexity is reduced from O(N.sup.3m) in algorithms 3.3 and 6.1 to O(N.sup.2 log m) in realization 10.

TABLE-US-00015 TABLE 5 Complexity Analysis of Montgomery MM Algorithms Complexity Cycle Clock Area Area-Time Count Period Cost Product realization 2 O(N/m) O (Nm) O (Nm) O (N.sup.3 m) realization 9 O(N/m) O (Nm) O (Nm) O (N.sup.3 m) realization 10 O(N/m) O (logm) O (Nm) O (N.sup.2 log m)

[0279] 2.5 Hardware Emulation Results

[0280] The proposed fixed-precision Montgomery MM design was coded in the Verilog hardware description language and implemented using the default flow of the Xilinx Vivado Virtex-7 xc7v585tffg1157-3 device, including synthesis and implementation. Instead of optimizing the realization for a specific value of m, our design maintains the flexibility to implement different m values, reflecting the trade-off between latency and area.

[0281] References [21] and [4] present two Montgomery MM designs that are parametric on m. When m doubles, the area roughly doubles whereas the cycle count is cut in half. However, the clock period also increases a lot. The period when m=8 is more than double that of m=2. Consequently, the area-time product (ATP) increases a lot when m increases.

[0282] Because of the modified Booth coding and the proposed Encode/EncodeSN, we eliminate half of the partial products. Meanwhile, the critical path of our design only depends on m so that the clock period does not change by much. The increase in the clock period is mainly due to the larger fan-out count and more challenging placement and routing problems when N changes from 1,024 to 2,048. Considering the configuration N=1,024 and m=8, compared with [21] and [4], our design reduces the computation latency by 49.53% and 46.09%, respectively, and the area by 31.97% and 36.33%, respectively. As a result, we save more than 65% in terms of the ATP metric. The advantages of our design in other configurations are also evident. When increasing m, the clock period gradually increases so that the savings in computation latency decrease accordingly. Based on the experimental results for our proposed Montgomery MM, we achieve the minimum value of the ATP metric for m=8. Finally, reference [18] provide a Montgomery MM design specifically optimized for the configuration N=2,048 and m=4. Compared with its synthesis results, our flexible design (which is parameterizable in m) achieves 29.77% reduction in the ATP. (see, Table 6, FIG. 29).

[0283] 3 Inventive Design of a High-Performance, Scalable Montgomery Modular Multiplier Circuit

[0284] It is desirable to design a high-performance, yet scalable, architecture for doing Montgomery modular multiplication. In the realization 8, both the quotient and intermediate result for each iteration are unsigned numbers so that it is not necessary to worry about the overflow problem mentioned in FIG. 16. Instead, both quotient and intermediate result of the realization 10 are signed numbers. This property gives rise to two problems: [0285] Once we apply intermediate result decomposition in section 5.1.2, the resulting ZM.sub.e-1 is a signed number whereas the lower significant words are unsigned numbers. We need a special task to complete the last iteration of the inner loop. [0286] Following the data model in FIG. 17, we can prevent any overflows of applying compression on the signed numbers by representing results in w+m+2 bits. In the last iteration of the inner loop, we need to fit the results in w+m bits but it would not be safe to simply truncate the leading 2 bits.

[0287] 3.1 Variant for a Different Input Range

[0288] As we discussed, the scalable design targets to compute Z=XYR.sup.−1modM when inputs X and Y and output Z all lie in the range [0,2M). This can be done easily by adjusting the number of iterations.

[0289] Intermediate result Z.sup.(i) satisfies the following relation:

Z.sup.(i)r.sup.i−1=XΣ.sub.k=0.sup.i{tilde over (Y)}.sub.kr.sup.k+MΣ.sub.k=0.sup.i−2{tilde over (q)}.sup.(k+1)r.sup.k  (75)

When (i+1)≥┌(N+2)/m┐, we have Σ.sub.k=0.sup.i {tilde over (Y)}.sub.kr.sup.k=Y so that

Z.sup.(i)r.sup.i−1=XY+MΣ.sub.k=0.sup.i−2{tilde over (q)}.sup.(k+1)r.sup.k  (76)

[0290] Based on equation (76), we can calculate the range of Z.sup.(i) as follows:

[00057]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i-1}& <4M^2+\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k\\ & <4M^2+\frac{2}{3}M\left(r-1\right)\frac{r^{i-1}-1}{r-1}\\ & <\left(4M+\frac{2}{3}{r}^{i-1}\right)M\\ Z^{\left(i\right)}& <\left(\frac{2}{3}+\frac{4M}{r^{i-1}}\right)M\\ Z^{\left(i\right)}{r}^{i-1}& \ge 0-\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k>\left(-\frac{2}{3}{r}^{i-1}\right)M\\ Z^{\left(i\right)}& >-\frac{2}{3}M>-M\end{array}& \left(77\right)\end{array}$

Therefore, when 4M/r.sup.d-2≤1/3 or 12M<r.sup.d-2, we have Z.sup.(d-1)∈(−M, M). We can set d=┌(N+4)/m┐+2 to ensure 12M<16M<2.sup.N+4≤2.sup.m(d-2)=r.sup.d-2. Realization 13 shows the details.

[0291] Since we prove Z.sup.(d-1)∈(−M, M), the final result Z=Z.sup.(d-1)+M∈(0,2M). Equation (78) generalizes the constraint:

md≥N+2m+4  (78)

When the number of iteration d meets the above equation, the final result Z lies in (0,2M).

TABLE-US-00016   Realization 13 Inventive fixed-precision radix-2.sup.m Mont- gomery modular multiplication: advanced version Input: X, Y ∈ [0, 2M), odd M < 2.sup.N, r = 2.sup.m,   d = ┌N + 4)/m┐ + 2, R = r.sup.d−2, r.sup.2r.sup.−1, − M M″ = 1   r.sup.2r.sup.−1 − M M″ = 1 Output: Z ∈ [0, 2M)  1: Z.sub.S.sup.(−1) = Z.sub.C.sup.(−1) = Z.sub.carry.sup.(−1) = q.sub.S.sup.(−1) = q.sub.C.sup.(−1) = q.sub.carry.sup.(−1) = 0  2: for i = 0 to d − 1 do  3: Z.sup.(i−1) = (Z.sub.S.sup.(i−1), Z.sub.C.sup.(i−1), Z.sub.carry.sup.(i−1))  4: Z.sub.L.sup.(i−1) = (Z.sub.S.sup.(i−1)[2m − 1 : 0], Z.sub.C.sup.(i−1)[2m − 1 :    0], Z.sub.carry.sup.(i−1))  5: Z.sub.L.sup.(i−1) = Encode(Z.sub.L.sup.(i−1))  6: q.sup.(i−1) = (q.sub.S.sup.(i−1), q.sub.C.sup.(i−1), q.sub.carry.sup.(i−1))  7: {tilde over (q)}.sup.(i−1) = Encode(q.sup.(i−1)), {circumflex over (q)}.sup.(i−1) = EncodeSN(q.sup.(i−1))  8: (q.sub.S.sup.(i), q.sub.C.sup.(i)) = Compress({tilde over (Z)}.sub.L.sup.(i−1) M″ − {circumflex over (q)}.sup.(i−1))  9: q.sub.carry.sup.(i) = q.sub.S.sup.(i)[m − 1] OR q.sub.C.sup.(i)[m − 1] 10: q.sub.S.sup.(i) = q.sub.S.sup.(i) >> m, q.sub.C.sup.(i) = q.sub.C.sup.(i) >> m 11: Y.sub.i = Y.sub.i − Y.sub.i[m − 1]r + Y.sub.i−1[m − 1] 12: (Z.sub.S.sup.(i), Z.sub.C.sup.(i)) = Compress(Z.sup.(i−1) + X{tilde over (Y)}.sub.ir.sup.2 + {circumflex over (q)}.sup.(i−1) M) 13: (Z.sub.S.sup.(i)[N + 3m] = (Z.sub.S.sup.(i)[N + 3m] XNOR Z.sub.C.sup.(i)[N + 3m] 14: Z.sub.C.sup.(i)[N + 3m] = 0 15: Z.sub.carry.sup.(i) = Z.sub.S.sup.(i)[m − 1] OR Z.sub.C.sup.(i)[m − 1] 16: Z.sub.S.sup.(i) = Z.sub.S.sup.(i) >> m, Z.sub.C.sup.(i) = Z.sub.C.sup.(i) >> m 17: end for 18: Z = Z.sub.S.sup.(d−1) + Z.sub.C.sup.(d−1) + Z.sub.carry.sup.(d−1) + M 19: return Z

TABLE-US-00017   Realization 14 Inventive fixed-precision radix-2.sup.m Mont- gomery modular multiplication after homogeneous decom- position Input: X, Y ∈ [0, 2M), odd M < 2.sup.N, r = 2.sup.m,  d = ┌(N + 4)/m┐ + 2, R = r.sup.d−2, r.sup.2r.sup.−1, − M M″ = 1 Output: Z ∈ [0, 2M)  1: ZSME.sup.(−2) = ZCME.sup.(−2) = 0  2: ZSME.sup.(−1) = ZCME.sup.(−1) = 0  3: ZSRE.sup.(−1) = ZCRE.sup.(−1) = 0  4: q.sub.S.sup.(−1) = q.sub.C.sup.(−1) = q.sub.carry.sup.(−1) = 0  5: for i = 0 to d − 1 do  6:  ZRE.sup.(i−1) = (ZSRE.sup.(i−1), ZCRE.sup.(i−1))  7:  ZME.sup.(i−2) = (ZSME.sup.(i−2), ZCME.sup.(i−2))  8:  (T.sub.S.sup.(i−1), T.sub.C.sup.(i−1))   =   Compress(ZRE.sup.(i−1) +     ZME.sup.(i−1)/r)  9:  Z.sub.L.sup.(i−1) = (T.sub.S.sup.(i−1)[2m − 1 : 0], T.sub.C.sup.(i−1)[2m − 1 :0]) 10:  {tilde over (Z)}.sub.L.sup.(i−1) = Encode(Z.sub.L.sup.(i−1)) 11:  q.sup.(i−1) = (q.sub.S.sup.(i−1), q.sub.C.sup.(i−1), q.sub.carry.sup.(i−1)) 12:  {tilde over (q)}.sup.(i−1) = Encode(q.sup.(i−1)), {circumflex over (q)}.sup.(i−1) = EncodeSN(q.sup.(i−1)) 13:  (q.sub.S.sup.(i), q.sub.C.sup.(i)) = Compress({tilde over (Z)}.sub.L.sup.(i−1) M″ − {circumflex over (q)}.sup.(i−1)) 14:  q.sub.carry.sup.(i) = q.sub.S.sup.(i)[m − 1] OR q.sub.C.sup.(i)[m − 1] 15:  q.sub.S.sup.(i) = q.sub.S.sup.(i) >> m, q.sub.C.sup.(i) = q.sub.C.sup.(i) >> m 16:  Y.sub.i = Y.sub.i − Y.sub.i[m − 1]r + Y.sub.i−1[m − 1] 17:  (Z.sub.S.sup.(i), Z.sub.C.sup.(i)) = Compress(X{tilde over (Y)}.sub.ir.sup.2 + {circumflex over (q)}.sup.(i−1)M +     ZRE.sup.(i−1) + ZME.sup.(i−2)/r) 18:  (Z.sub.S.sup.(i)[N + 3m] = (Z.sub.S.sup.(i)[N + 3m] XNOR Z.sub.C.sup.(i)[N + 3m] 19:  Z.sub.C.sup.(i)[N + 3m] = 0 20:  Z.sub.carry.sup.(i) = Z.sub.S.sup.(i)[m − 1] OR Z.sub.C.sup.(i)[m − 1] 21:  (ZSME.sup.(i), ZSRE.sup.(i)) = Decomposed(Z.sub.S.sup.(i) >> m) 22:  (ZCME.sup.(i), ZCRE.sup.(i)) = Decomposed(Z.sub.C.sup.(i) >> m) 23:  TAIL(ZCRE.sub.0.sup.(i), Z.sub.carry.sup.(i) 24: end for 25: Z = ZSME.sup.(d−2) /r + ZSME.sup.(d−2) /r + ZSME.sup.(d−1) +   ZSME.sup.(d−1) + ZSRE.sup.(d−1) + ZCRE.sup.(d−1) + M 26: return Z

[0292] 3.2 Homogeneous Decomposition of the Intermediate Result

[0293] Taking a closer look at realization 13, it can be seen that we only need the 2m least significant bits of Z.sub.S.sup.(i−1) and Z.sub.C.sup.(i−1) to compute q.sup.(i). We may decompose both Z.sub.S.sup.(i−1) and Z.sub.C.sup.(i−1) into e words where each word has w bits (see the discussion of e below). In this case, the most significant word is a signed number whereas the remaining (lower significant) words are unsigned numbers. Instead, we extend the decomposition for Z (Z.sub.S or Z.sub.C in any iteration) into e words as shown below:

[00058]$\begin{array}{cc}\begin{array}{cc}Z& =-Z\left[N+2m\right]2^{N+2m}+\underset{i=0}{\overset{N+2m-1}{.Math.}}Z\left[i\right]2^i\\ & =\underset{i=0}{\overset{e-1}{.Math.}}\left({\mathrm{ZE}}_i\right)2^{\mathrm{wi}}\\ {\mathrm{ZE}}_i& =\underset{k=0}{\overset{w-2}{.Math.}}Z\left[\mathrm{iw}+k\right]2^k-Z\left[\left(i+1\right)w-1\right]2^{w-1}\\ & +Z\left[\mathrm{iw}-1\right]\end{array}& \left(79\right)\end{array}$

Notice that Z[i]=Z[N+2m] for i≥N+2m to perform sign extension and Z[−1]=0.

[0294] In this case, Z is homogeneously decomposed into words ZE.sub.i for 0≤i≤e−1. Each ZE.sub.i is a w-bit signed number and a 1-bit unsigned tail number such that: Z=Σ.sub.i=0.sup.e-1 (ZE.sub.i)2.sup.wi. We can further decompose ZE.sub.i into two parts ZME.sub.i and ZRE.sub.i as shown in (80). The least w−m bits of ZME.sub.i are 0 and the most m bits of ZRE.sub.i are 0. When w≥3m and w−m≥2m, we only need ZRE (more precisely ZRE.sub.0) to compute q.

ZE.sub.i=ZME.sub.i+ZRE.sub.i

ZME.sub.i=Σ.sub.k=w-m.sup.w-1Z[iw+k]2.sup.k−Z[(i+1)w−1]2.sup.w-1

ZRE.sub.i=Σ.sub.k=0.sup.w-m-1Z[iw+k]2.sup.k+Z[iw−1]

Z=ZME+ZRE

ZME=Σ.sub.i=0.sup.e-1ZME.sub.i2.sup.wi

ZRE=Σ.sub.i=0.sup.e-1ZRE.sub.i2.sup.wi  (80)

[0295] Realization 14 shows the Montgomery modular multiplication after the aforesaid homogeneous decomposition. We simply place Z.sub.carry.sup.(i) in the following bit of ZCRE.sub.0.sup.(i), say TAIL(ZCREV.sub.0.sup.(i)).

[0296] 3.3 Scalable Architecture

[0297] Similar to realization 8, we use an inner loop in realization 15 to do the operation Compress(X{tilde over (Y)}.sub.ir.sup.2+{tilde over (q)}.sup.(i−1)M+ZRE.sup.(i−1)+ZME.sup.(i−1)/r) by scanning w bits of X′=Xr.sup.2, M, ZRE.sup.(i−1), and ZME.sup.(1-1) in each iteration.

TABLE-US-00018 Realization 15 Inventive scalable radix-2.sup.m Montgomery modular multiplication (MWR2tm) Input: X, Y ∈ [0, 2M), X′ = Xr.sup.2, odd M < R = r.sup.kp−2,   [00059]$r=2^m,r^2{r}^{-1}-{\mathrm{MM}}^{″}=1,w\ge 2m,e=.Math.\frac{N+2m+3}{w}.Math.,$   [00060]$k=.Math.\frac{N+2m+4}{mp}.Math.,p=\mathrm{PE}\mathrm{count}$ Output: Z ∈ [0, 2M)  1: ZSME′ = 0, ZSME = 0, ZSRE = 0  2: ZCME′ = 0, ZCME = 0, ZCRE = 0,  3: qs = 0, qc = 0, q.sub.carry = 0  4: for i = 0 to kp − 1 do {/ /outer loop}  5:  FBS = FBC = 0  6:  for j = 0 to e − 1 do {/ /inner loop}  7:   (TS, TC) = Compress(ZSRE.sub.j + ZCRE.sub.j + ZSME.sub.j′/r +     ZCME.sub.j′/r)  8:   if j = = 0 then  9:    Z.sub.L = (T.sub.S[2m − 1:0], T.sub.C[2m − 1:0]) 10:    Z.sub.L = Encode(Z.sub.L) 11:    q = (q.sub.S, q.sub.C, q.sub.carry) 12:    q = Encode(q), {circumflex over (q)} = EncodeSN(q) 13:    (q.sub.S, q.sub.C) = Compress({tilde over (Z)}.sub.LM″ − {circumflex over (q)}) 14:    q.sub.carry = q.sub.S[m − 1] OR q.sub.C[m − 1] 15:    q.sub.S = q.sub.S >> m, q.sub.C = q.sub.C >> m 16:   end if

[0298] 3.3.1 Inner Loop Computations

[0299] In the first iteration of the inner loop (j=0), we need to compute the sum of ZSRE.sub.0, ZCRE.sub.0, ZSME.sub.0/r, ZCME.sub.0/r, X′.sub.0{tilde over (Y)}.sub.i, and {tilde over (q)}M.sub.0. Notice that they are signed numbers. We can use two (w+x)-bit signed numbers OS and OC (x≥0) to accurately represent the sum. Based on the least w bits, we can compute ZSRE.sub.0 and ZCRE.sub.0 as in (81). Notice that OS+OC is a multiple of r, we can embed Z.sub.carry=OS[m−1]OROC[m−1] to the tail bit of ZCRE.sub.0. The leading x bits of OS and OC are stored in FBS and FBC for future reference.

[00061]$\begin{array}{cc}\begin{array}{cc}{\mathrm{ZSRE}}_0+{\mathrm{ZCRE}}_0& =\frac{\mathrm{OS}\left[w-1:0\right]+\mathrm{OC}\left[w-1:0\right]}{r}\\ & =\mathrm{OS}\left[w-1:m\right]+\mathrm{OC}\left[w-1:m\right]\\ & +Z_{\mathrm{carry}}\end{array}& \left(81\right)\end{array}$

[0300] In the second iteration (j=1), we need to compute the sum of ZSRE.sub.1, ZCRE.sub.1, ZSME.sub.1/r, ZCME.sub.1/r, X′.sub.1{tilde over (Y)}.sub.i, qM.sub.1, FBS, and FBC. Again, we represent them into two (w+x)-bit signed number OS and OC. Based on the least w bits and the homogeneous decomposition in (80), we can compute ZSRE.sub.1/ZCRE.sub.1 and ZSME.sub.0/ZCME.sub.0. The leading x bits of OS and OC are again stored in FBS and FBC for future reference.

ZSME.sub.0=Σ.sub.k=0.sup.m−2OS[k]2.sup.w-m+k−OS[m−1]2.sup.w-1

ZCME.sub.0=Σ.sub.k=0.sup.m−2OC[k]2.sup.w-m+k−OC[m−1]2.sup.w-1

ZSRE.sub.1=OS[w−1: m]+OS[m−1]

ZCRE.sub.1=OC[w−1: m]+OC[m−1]  (82)

[0301] The next question is what bitwidth w+x for OS and OC is sufficient to accurately represent intermediate results in each iteration of the inner loop. Following the data model in FIG. 17 and optimization in FIG. 18, we can prove that setting x=m+3 will suffice. Since OS[w+m+2] and OS[w+m+1] are the same, we may hide OS[w+m+2].

[0302] 3.3.2 Scheduling and Computation of e

[0303] FIG. 20 shows the data dependency graph, where we can issue a new word of multiplier {tilde over (Y)}.sub.i every cycle. In the A task, we compute quotient q and intermediate result ZSRE.sub.0 and ZCRE.sub.0. In each of the B tasks, we compute ZSRE.sub.j and ZCRE.sub.j, ZSME.sub.j-1, and ZCME.sub.j-1.

[0304] FIG. 20(a) shows the schedule when we have 3 PEs to finish the computation in 3 rounds. In the A task of the second round of PE, we generate ZSRE.sub.0 and ZCRE.sub.0 and also generate ZSME.sub.e-1 and ZCME.sub.e-1 for the first round. Since we generate w bits every cycle, we actually try to fit intermediate result into ew+m bits. Based on the number of PE instances, we can compute the number of cycles as shown below:

[00062]$\begin{array}{cc}\mathrm{cycle\_cnt}=(\begin{array}{cc}\mathrm{kp}+e+1& \mathrm{ife}\le p\\ \mathrm{ke}+p+1& \mathrm{otherwise}\end{array}& \left(83\right)\end{array}$

[0305] 3.3.3 Overflow Correction

[0306] Ideally, we can generate w bits of the intermediate result until the last iteration j=e−1, in which we compute ZSRE.sub.e-1, ZCRE.sub.e-1, ZSME.sub.e-2, and ZCME.sub.e-2. If we use the whole m+2 bits of FBS and FBC to represent ZSME.sub.e-1 and ZCME.sub.e-1, we can accurately represent the data without overflow. However, it is dangerous to directly take m bits to fit ZSME.sub.e-1 and ZCME.sub.e-1. FIG. 24 shows an example. If we finish the addition, the sum is a negative number, but if we directly use the 4 least significant bits, ZSME.sub.e-1 and ZCME.sub.e-1 become positive and thus cause overflow. We need a method to correct the potential overflow.

[0307] Fortunately, we just need a 2-bit addition to correct the overflow. FIG. 25 shows our data model. Assume we have two (N+1)-bit signed number Z.sub.S and Z.sub.C and we know the sum Z is an N-bit signed number, we just need one addition on the leading 2 bits. Since Z is a N-bit signed number, Z[N] must be the sign extension and Z[N]=Z[N−1].

[0308] Once we do the addition and ignore any overflow, we can deduce the possible carry C.sub.in for the least N−1 bits as shown in table 7. When (c.sub.1, c.sub.0)=(0,0), C.sub.in has to be 0 and Z[N]=Z[N−1]=0. C.sub.in cannot be 1, otherwise Z[N]≠Z[N−1]. Similarly, C.sub.in is 1 when (c.sub.1, c.sub.0)=(1,0). The case when (c.sub.1, c.sub.0)=(0,1) is impossible since Z[N] is always different from Z[N−1] no matter what C.sub.in is. When (c.sub.1, c.sub.0)=(1,1), C.sub.in can be 0 or 1. Except for the case (c.sub.1, c.sub.0)=(0,1), the remaining cases will not cause overflow and thus accurately represent the final sum Z.

TABLE-US-00019 TABLE 7 Truth table for the overflow correction c.sub.1 c.sub.0 C.sub.in 0 0 0 0 1 N.A. 1 0 1 1 1 0/1

[0309] We can use the data model in FIG. 25 to compute ZSME.sub.e-1 and ZCME.sub.e-1. redEquation (84) shows that the intermediate result Z.sup.(i) (after division by r) is an (N+2m+2)-bit signed number.

[00063]$\begin{array}{cc}\begin{array}{cc}{Z}^{\left(i\right)}{r}^{i-1}& =X\underset{k=0}{\overset{i}{.Math.}}{\tilde{Y}}_k{r}^k+M\underset{k=0}{\overset{i-2}{.Math.}}{\tilde{q}}^{\left(k+1\right)}{r}^k\\ .Math.Z^{\left(i\right)}{r}^{i-1}.Math.& <2M\frac{r^{i+1}}{2}+\frac{2}{3}M\left(r-1\right)\underset{k=0}{\overset{i-2}{.Math.}}{r}^k\\ & <2M\left(\frac{r^{i+1}}{2}+\frac{2}{3}{r}^{i-1}\right)\\ .Math.Z^{\left(i\right)}.Math.& <M\left(r^2+\frac{2}{3}\right)<2^{N+2m+1}\end{array}& \left(84\right)\end{array}$

[0310] We thus require ew+m≥(N+3m+2)+1.

[00064]$\begin{array}{cc}e=.Math.\frac{N+2m+3}{w}.Math.& \left(85\right)\end{array}$

[0311] Assume we instantiate p PEs and go through them k rounds, we equivalently finish kp iterations of the outer loop. Based on equation (78), we have

[00065]$\begin{array}{cc}m\left(\mathrm{kp}\right)\ge N+2m+4k=.Math.\frac{N+2m+4}{\mathrm{mp}}.Math.& \left(86\right)\end{array}$

Since e is large enough, we just need to add FBS[m−1: m−2] and FBC[m−1: m−2] and then assign the summation results to ZSME.sub.e-1/ZCME.sub.e-1.

[0312] 3.3.4 Hardware Implementation

[0313] FIG. 22 shows the implementation of processing elements to do tasks A and B. In task A (CT=1), we perform the following operations: [0314] compute {tilde over (Z)}.sub.L and {circumflex over (q)} and compute q.sub.S, q.sub.C, and q.sub.carry; [0315] compute {tilde over (q)} and compress {tilde over (q)}M.sub.0+X′.sub.0{tilde over (Y)}.sub.i+ZSME′.sub.0/r+ZCME′.sub.0/r+ZSRE.sub.0+ZCRE.sub.0; [0316] generate results ZSRE.sub.0 and ZCRE.sub.0; [0317] generate results ZSRE.sub.e-1 and ZCRE.sub.e-1 for the previous iteration based on the value stored in FBS and FBC; and [0318] update FBS and FBC.

[0319] In task B (CT=0), we perform the following operations: [0320] compress {tilde over (q)}M.sub.j+X′.sub.j{tilde over (Y)}.sub.i+ZSME′.sub.j/r+ZCME′.sub.j/r+ZSRE.sub.j+ZCRE.sub.j+FBS+FBC based on the stored {tilde over (q)}; [0321] generate results ZSRE.sub.j, ZCRE.sub.j, ZSME.sub.j-1, and ZCME.sub.j-1; and [0322] update FBS and FBC.

[0323] Unlike the A and B tasks, the C task needs only one special processing element (named PEc). FIG. 26 shows the implementation of the PEc. When CT=1, we force feedback signals DO1 and DO2 to 0 and set the carry signal as 0. When CT=0, we accept feedback signals DO1 and DO2 and set the carry signal as the carry-out bit from the previous cycle.

[0324] We also show the block-level architecture of the proposed high-performance, radix-2.sup.m scalable Montgomery modular multiplication in FIG. 23. The required ZSME′.sub.j and ZCME′.sub.j in the i-th outer loop iteration in realization 8 are actually ZSME.sub.j and ZCME.sub.j which are generated in the (i−2)-nd outer loop iteration. Similarly, ZSME′.sub.j and ZCME′.sub.j required in the PEc are ZSME.sub.j and ZCME.sub.j generated by the next to the last PE. To compute Z.sub.j, we need ZSME′.sub.j, ZCME′.sub.j, ZSME.sub.j, ZCME.sub.j, ZSRE.sub.j, ZCRE.sub.j. However, they are not generated in the same cycle. More precisely, ZSME.sub.j and ZCME.sub.j are generated in the (j+1)-st inner loop iteration whereas ZSME′.sub.j, ZCME′.sub.j, ZSRE.sub.j, and ZCRE.sub.j are generated in the j-th inner loop iteration and need to be delayed by one clock cycle as shown in FIG. 26. When p<e as in FIG. 21(b), a first-in first-out queue with a depth of e−p slots is necessary to buffer the outputs.

[0325] 3.3.5 Pipelining

[0326] The design in section 7.3.4 finishes each iteration of the inner loop in one cycle. Instead, we can pipeline the processing element in FIG. 22 into 2 stages or more. Once the connections among different PEs are adjusted accordingly, we can achieve an issue latency (L) of 2 or more. Equation (87) generalizes the number of cycles.

[00066]$\begin{array}{cc}\mathrm{cycle\_cnt}=(\begin{array}{cc}\mathrm{kLp}+e+1& \mathrm{ife}\le \mathrm{Lp}\\ \mathrm{ke}+\mathrm{Lp}+1& \mathrm{otherwise}\end{array}& \left(87\right)\end{array}$

[0327] Although the number of cycles increases when L is more than 1, the required number of PEs (which is optimal for a specified bitwidth N) is reduced to e/L which results in area savings. If we balance the delay in each stage of the pipeline, the impact on the full circuit latency will be minimized.

[0328] Additional details of some aspects of the invention are set forth in B. Zhang, Z. Cheng and M. Pedram, “High-Radix Design of a Scalable Montgomery Modular Multiplier with Low Latency,” in IEEE Transactions of Computers, doi: 10.1109/TC.2021.3052999; the entire disclosure of which is hereby incorporated by reference.

[0329] While exemplary embodiments are described above, it is not intended that these embodiments describe all possible forms of the invention. Rather, the words used in the specification are words of description rather than limitation, and it is understood that various changes may be made without departing from the spirit and scope of the invention. Additionally, the features of various implementing embodiments may be combined to form further embodiments of the invention.

REFERENCES

[0330] [1] Dorian Amiet, Andreas Curiger, and Paul Zbinden. Flexible fpga-based architectures for curve point multiplication over gf (p). In 2016 Euromicro Conference on Digital System Design (DSD), pages 107-114. IEEE, 2016. [0331] [2] Richard P Brent and Hsiang T Kung. A regular layout for parallel adders. IEEE Computer Architecture Letters, 31(03):260-264, 1982. [0332] [3] Viktor Bunimov and Manfred Schimmler. Area and time efficient modular multiplication of large integers. In Proceedings IEEE International Conference on Application-Specific Systems, Architectures, and Processors. ASAP 2003, pages 400-409. IEEE, 2003. [0333] [4] Serdar Süer Erdem, Tuğrul Yanik, and Anil Çelebi. A general digit-serial architecture for montgomery modular multiplication. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25(5):1658-1668, 2017. [0334] [5] Sahar Fatemi, Maryam Zare, Amir Farzad Khavari, and Mohammad Maymandi-Nejad. Efficient implementation of digit-serial montgomery modular multiplier architecture. IET Circuits, Devices & Systems, 13(7):942-949, 2019. [0335] [6] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169-178, 2009. [0336] [7] Zhen Gu and Shuguo Li. A division-free toom-cook multiplication-based montgomery modular multiplication. IEEE Transactions on Circuits and Systems II: Express Briefs, 66(8):1401-1405, 2018. [0337] [8] Gaël Hachez and Jean-Jacques Quisquater. Montgomery exponentiation with no final subtractions: Improved results. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 293-301. Springer, 2000. [0338] [9] David Harris, Ram Krishnamurthy, Mark Anders, Sanu Mathew, and Steven Hsu. An improved unified scalable radix-2 montgomery multiplier. In 17th IEEE Symposium on Computer Arithmetic (ARITH'05), pages 172-178. IEEE, 2005. [0339] [10] Miaoqing Huang, Kris Gaj, and Tarek El-Ghazawi. New hardware architectures for montgomery modular multiplication algorithm. IEEE Transactions on computers, 60(7):923-936, 2010. [0340] [11] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation, 48(177):203-209, 1987. [0341] [12] Ciaran Mclvor, Maire McLoone, and John V McCanny. Fast montgomery modular multiplication and rsa cryptographic processor architectures. In The Thirty-Seventh Asilomar Conference on Signals, Systems & Computers, 2003, volume 1, pages 379-384. IEEE, 2003. [0342] [13] NIEL Michael. Montgomery multiplication method, Feb. 17, 2015. U.S. Pat. No. 8,959,134. [0343] [14] Peter L Montgomery. Modular multiplication without trial division. Mathematics of computation, 44(170):519-521, 1985. [0344] [15] Miguel Morales-Sandoval and Arturo Diaz-Perez. Scalable gf (p) montgomery multiplier based on a digit-digit computation approach. IET Computers & Digital Techniques, 10(3):102-109, 2016. [0345] [16] Michael Andrew Moshier and Jeff Furlong. Scalable, faster method and apparatus for montgomery multiplication, Sep. 28, 2010. U.S. Pat. No. 7,805,479. [0346] [17] Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM workshop on Cloud computing security workshop, pages 113-124, 2011. [0347] [18] Bien-Cuong Nguyen and Cong-Kha Pham. An efficient hardware implementation of radix-16 montgomery multiplication. In 2019 IEEE 8th Global Conference on Consumer Electronics (GCCE), pages 1121-1122. IEEE, 2019. [0348] [19] Holger Orup. Simplifying quotient determination in high-radix modular multiplication. In Proceedings of the 12th Symposium on Computer Arithmetic, pages 193-199. IEEE, 1995. [0349] [20] Erdem Özcan and Serdar S Erdem. A fast digit based montgomery multiplier designed for fpgas with dsp resources. Microprocessors and Microsystems, 62:12-19, 2018. [0350] [21] Jeng-Shyang Pan, Pengfei Song, and Chun-Sheng Yang. Efficient digit-serial modular multiplication algorithm on fpga. IET Circuits, Devices & Systems, 12(5):662-668, 2018. [0351] [22] Ronald L Rivest, Len Adleman, Michael L Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169-180, 1978. [0352] [23] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126, 1978. [0353] [24] Sudhir K Satpathy, Raghavan Kumar, Sanu K Mathew, and Vikram B Suresh. Parallel computation techniques for accelerated cryptographic capabilities, Dec. 3, 2019. U.S. Pat. No. 10,498,532. [0354] [25] Ming-Der Shieh and Wen-Ching Lin. Word-based montgomery modular multiplication algorithm for low-latency scalable architectures. IEEE transactions on computers, 59(8):1145-1151, 2010. [0355] [26] Alexandre F Tenca and Çetin K Koç. A scalable architecture for modular multiplication based on montgomery's algorithm. IEEE Transactions on computers, 52(9):1215-1221, 2003. [0356] [27] Colin D Walter. Montgomery's multiplication technique: How to make it smaller and faster. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 80-93. Springer, 1999. [0357] [28] Tao Wu, ShuGuo Li, and LiTian Liu. Fast rsa decryption through high-radix scalable montgomery modular multipliers. Science China Information Sciences, 58(6):1-16, 2015.