Patent ID: 7395295

Claim:
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.