Pipeline core in Montgomery multiplier
View Patent ↗A multiplier apparatus is arranged for multiplying a first long integer entity with a second long integer entity modulo a prime number. In particular, the comprises a pipelined multiplier core, whilst executing the overall multiplication in Montgomery fashion.
1. A multiplier apparatus that is arranged for multiplying a first long integer entity with a second long integer entity modulo a prime number, which the apparatus is characterized by comprising a pipelined multiplier core, whilst executing the overall multiplication in Montgomery fashion, wherein the apparatus comprises:
first registers to receive a first n-bit operand X;
second registers to receive a second n-bit operand Y;
third registers to receive a third n-bit operand W; and
means for executing multiplications and additions on bits associated with the first n-bit operand X, the second n-bit operand Y and the third n-bit operand W from the first, second and third registers, the executing means being configured to sequentially perform an operation defined by Z i =X*y+Z i−1 , where i has a range from 0 to a predefined number equal to n/2-1, X represents the first n-bit operand X, y represents one or more bits of the second n-bit operand Y and Z 0−1 is the third n-bit operand W, the executing means being further configured to produce an n-bit output Z using the bits from Z i when i equals the predefined number n/2-1.
2. An apparatus as claimed in claim 1 , furthermore being arranged for implementing a modified Booth algorithm.
3. An apparatus as claimed in claim 1 , and being arranged for multiplying said first and second integer entities in the form of respective polynomials, and modulo an irreducible polynomial in a Galois Field GF(2 n ).
4. An apparatus as claimed in claim 1 and applied to executing an RSA-like Calculation.
5. An apparatus as claimed in claim 1 , and applied to executing an Elliptic Curve Calculation.
6. An apparatus as claimed in claim 1 , wherein the executing means is further configured to add upper n-bits of Z i and lower n-bits of Z i when i equals the predefined number n/2-1 to derive the n-bit output Z.
7. An apparatus as claimed in claim 1 , wherein the executing means is further configured to subtract an artifact of the operation defined by Z i =X*y+Z i−1 from one or more Z i 's.
8. A multiplier apparatus for multiplying a first long integer entity with a second long integer entity modulo a prime number, the apparatus comprising:
first registers to receive a first n-bit operand X;
second registers to receive a second n-bit operand Y;
third registers to receive a third n-bit operand W; and
a plurality of adders and multipliers to execute multiplications and additions on bits associated with the first n-bit operand X, the second n-bit operand Y and the third n-bit operand W from the first, second and third registers, the plurality of adders and multipliers being configured to sequentially perform an operation defined by Z i =X*y+Z i−1 , where i has a range from 0 to a predefined number equal to n/2-1, X represents the first n-bit operand X, y represents one or more bits of the second n-bit operand Y and Z 0−1 is the third n-bit operand W, the plurality of adders and multipliers being further configured to produce an n-bit output Z using the bits from Z i , when i equals the predefined number n/2-1.
9. An apparatus as claimed in claim 8 , furthermore being arranged for implementing a modified Booth algorithm.
10. An apparatus as claimed in claim 8 , and being arranged for multiplying said first and second integer entities in the form of respective polynomials, and modulo an irreducible polynomial in a Galois Field GF(2 n ).
11. An apparatus as claimed in claim 8 and applied to executing an RSA-like Calculation.
12. An apparatus as claimed in claim 8 , and applied to executing an Elliptic Curve Calculation.
13. An apparatus as claimed in claim 8 , wherein the plurality of adders and multipliers is further configured to add upper n-bits of Z i and lower n-bits of Z i when i equals the predefined number n/2-1 to derive the n-bit output Z.
14. An apparatus as claimed in claim 8 , wherein the plurality of adders and multipliers is further configured to subtract an artifact of the operation defined by Z i =X*y+Z i−1 from one or more Z i 's.