Patent ID: 8233615

Claim:
A modular reduction method performed by an elliptic curve cryptography system that includes a processor and memory, the method using a modified form of a Barrett reduction method based on elliptic curves on a prime field comprising: obtaining input specifying a first value U to reduce; obtaining input specifying a modulus N, wherein the modulus N is of a special form; performing a modular reduction of the first value U modulo the special form of the modulus N, wherein the modular reduction comprises: calculating an estimated form of a first quotient q^ using the modulus of the special form N; calculating an estimated form of a second quotient q3^; substituting the estimated form of the first quotient q^ with the estimated form of the second quotient q3^; calculating an estimated form of a remainder r3^; and calculating an estimated reduced form of the first value U based on the estimated form of the second quotient q3^ and the estimated form of the remainder r3^.