Patent ID: 6917956

Claim:
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 n s n−1 . . . s 1 s 0 ) b and T=(t n t n−1 . . . t 1 t 0 ) b .) b. For i from 0 to (n−1), do the following: b1. u i ←(s 0 +t 0 +x i y 0 ) m′ mod b b2. (S, T)←(S+T+x i y+u i m)/b c. A 1 ←S+T and A 2 ←S+T−m d. If A 2 ≧0 then A←A 2 else A←A 1 e. Return A.