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: a first calculator operable to calculate an "Almost Montgomery Inverse" of a first input variable; a counter z; a second calculator operable to calculate a Montgomery modular product of the output from the first calculator and the second input variable in the event that z=k; a third calculator operable to calculate a Montgomery modular product of the output of the first calculator and 2^2*k-z in the event that z<>k; a fourth calculator operable to calculate a Montgomery modular product of the output from the third calculator and the second input variable in the event that z<>k; and further comprising a selector for 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.