Patent ID: 7693926

Claim:
A method to process multiplier X and multiplicand Y, comprising: multiplying, via a processing element, a least-significant bit of X and a least-significant w bits of Y to generate a least-significant w bits of product Z; determining if a least-significant bit of product Z is 1; adding a least-significant w bits of modulus M to the least-significant w bits of product Z if the least-significant bit of product Z is 1; multiplying the least-significant bit of X and bits 2 w- 1 :w of Y to generate bits 2 w- 1 :w of product Z; and adding bits 2 w- 1 :w of modulus M to bits 2 w- 1 :w of product Z if the least-significant bit of product Z is 1, wherein multiplying the least-significant bit of X and bits 2 w- 1 :w of Y occurs at least partially contemporaneously with multiplying the least-significant bit of X and the least-significant w bits of Y, determining if the least-significant bit of product Z is 1, and adding the least-significant w bits of modulus M to the least-significant w bits of product Z if the least-significant bit of product Z is 1.