Patent ID: 7978846

Claim:
A method comprising: computing, by a public key encryption unit, an N-bit scaled reduction parameter based on a k-bit modulus m, N being greater than k; and performing a Barrett Reduction using the N-bit scaled reduction parameter on an N-bit scaled result generated using an N-bit scaled modulus to reduce the N-bit scaled result to a k-bit result with respect to the k-bit modulus m, the performing comprising: multiplying the N-bit scaled reduction parameter by the N-bit scaled result to provide a 2N-bit first product; shifting the first product by N-bits to provide a shifted first product; multiplying m by the shifted first product to provide a second product; subtracting the second product from the N-bit scaled result to provide an intermediate value R; subtracting m from the intermediate value R while the intermediate value R is greater than m; providing the intermediate value R as the k-bit result; and storing the k-bit result in a memory for use by a processor.