Patent ID: 6917956
Filing Date: 2005-07-12
Classification: G06F

Abstract:
1. In a Montgomery multiplication algorithm, a method of computing an output xyR −1 mod m from input integers m=(m n−1 . . . m 1 m 0 ) b , x=(x n−1 . . . x 1 x 0 ) b , y=(y n−1 . . . y 1 y 0 ) b , with 0≦x, y<m, R=b n with gcd(m, b)=1, and m′=−m −1 mod b comprising the steps of: representing a value A in the Montgomery multiplication algorithm with a redundant notation; and performing carry-save addition within an iterative process of the Montgomery multiplication algorithm to compute a new value of A, and further comprising executing the algorithm: a. S←0 and T←0 (where S=(s b. For i from 0 to (n−1), do the following: c. A d. If A e. Return A.