Patent ID: 8433736

Claim:
A Montgomery multiplication process for obtaining a Montgomery product of a first operand X and a second operand Y with respect to a modulus M in a Montgomery multiplication device having a plurality of processing elements which are interconnected in sequence, said Montgomery multiplication process comprising: a) selecting a word length w and a number of words e; b) scanning said second operand Y and said modulus M as e words of length w, wherein e is at least 2; c) scanning said first operand X as n bits; d) in a first clock cycle of at least one of said plurality of processing elements: (1) creating a first intermediate partial sum of length w by: (a) obtaining a parameter of length w−1 precalculated in said at least one of said plurality of processing elements as w−1 least significant bits of said first intermediate partial sum; and (b) configuring the most significant bit of said first intermediate partial sum as zero; (2) creating a second intermediate partial sum by: (a) obtaining said parameter as the w−1 least significant bits of said second intermediate partial sum; and (b) configuring the most significant bit of said second intermediate partial sum as one; (3) calculating a first partial sum bits using at least: (a) a word of said second operand Y; (b) a word of said modulus M; (c) a bit of said first operand X; and (d) said first intermediate partial sum; (4) calculating a second partial sum bits using at least: (a) a word of said second operand Y; (b) a word of said modulus M; (c) a bit of said first operand X; and (d) said second intermediate partial sum; and e) in a second clock cycle of at least one of said plurality of processing elements: i) obtaining a selection bit from a subsequent processing element in said plurality of processing elements; ii) selecting either said first partial sum or said second partial sum as a selected partial sum based on the value of said selection bit; and iii) using said selected partial sum for calculation of a word of said Montgomery product.