Method and apparatus for calculating a modular inverse

摘要

Apparatus for calculating a classical modular inverse or a Montgomery modular inverse of an integer a (mod p), where p is a k-bit integer, comprising:
(1) a first calculating means operable to calculate an "Almost Montgomery Inverse" of a first input variable;
(2) a counting means z;
(3) a second calculating means operable to calculate a Montgomery modular product of the output from the first calculating means and the second input variable in the event that z=k;
(4) a third calculating means operable to calculate a Montgomery modular product of the output of the first calculating means and 2 2* k-z in the event that z‰ k;
(5) a fourth calculating means operable to calculate a Montgomery modular product of the output from the third calculating means and the second input variable in the event that z‰ k;
€ƒ€ƒ€ƒand further comprising a means of selecting a first and second input variable when calculating the classical modular inverse being different from the first and second input variables selected when calculating the Montgomery modular inverse.