| 摘要 |
Methods and apparatus are described for computing modular inverses of odd input values modulo 2N (or modulo xN, for example in some Galois field) to perform a modular multiplication in cryptographic processing systems. In one embodiment an approximation is computed having 2k bits of the modular inverse of the odd input value without multiplications, for example using a binary extended Euclidean algorithm. A sequence of log2N−k Newton-Raphson or similarly quadratically convergent iterations are applied to the approximation using an extended precision multiplier to generate the modular inverse of the odd input value modulo 2N (or modulo xN), the modular inverse having up to N bits of precision. The modular inverse of the odd input value is then used in a modular multiplication to perform cryptographic operations and/or cyclic redundancy checks on communication data.
|
