Patent ID: 7532720

Claim:
A processing system comprising: a processor having a set of registers; and the processor executes a set of SIMD instruction to perform Montgomery multiplication: montmul( A, B )=rem(( AB−qN )/ R, N ), where q=rem( AB N′, R; where A and B are integers, q is a quotient, N is a modulus, R is an integer that is coprime to modulus N, and N′ is an integer such that NNT′≡1 (mod R), wherein the integer B and the modulus N are implemented as arrays, and at least one SIMD instruction is used to update a first array T 1 with multiples of B for computing AB and to update a second array T 2 with multiples of N for computing qN, wherein a first register holds elements of the B and N arrays; a second register holds an element of the first array T 1 and an element of the second array T 2 ; and a third register is used to hold results of the first array T 1 being updated with a multiple of B and the second array T 2 being updated with multiples of N.