Patent ID: 8392494

Claim:
A method comprising: operable on one or more processors; storing a state of a fold carry bit resulting from a result of a fold operation to reduce an a-bit number A to a b-bit number B wherein the b-bit number B is reduced modulus m to an n-bit number R, b equal to (t+n) and t less than n, using Barrett Reduction; using the stored state of the fold carry bit to retrieve a pre-computed constant number corresponding to the state of the fold carry bit and position of the fold carry bit with respect to A, the pre-computed constant used to reduce the b-bit number B modulus m in a time-invariant manner to an r-bit result R; performing time-invariant Barrett Reduction comprising: converting 129-bit operands to 128-bit sized operands; performing a multiplication by two of an addition term using pre-computed conversion constant numbers stored in a table; and performing a fixed number of subtraction operations.