IEEE Transactions on Computers · 2008 · 16 citations · 6 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureTheory Of ComputationAlgorithm AnalysisComputational ComplexityModular ArithmeticArithmetic Of Finite FieldsExponentiation AlgorithmsModular InversionModular Inversion AlgorithmsProcessor Systems
This paper presents a procedure for calculating multiplicative inverses Modulo 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> , based on a novel mathematical approach. The procedure is suitable for software implementation on a general-purpose processor. When counting the total number of word-level processor multiplications, the computational effort involved in calculating a multiplicative inverse is 2/3 that of a single multiplication of m-bit values, in addition to a few word-level multiplications. For standard processor word sizes, the number of these additional multiplications does not exceed 12. This introduces a clear advantage of the proposed method when compared to other known methods presented in the literature.
6
Modular multiplication without trial division
Peter L. Montgomery · Mathematics of Computation · 1985 · 2.4K citations
Modular Multiplication Without Trial Division
Peter L. Montgomery · Mathematics of Computation · 1985 · 1.1K citations · Full text
The Montgomery inverse and its applications
Burton S. Kaliski · IEEE Transactions on Computers · 1995 · 172 citations
The Montgomery modular inverse-revisited
Erkay Savaş, Çetin Kaya Koç · IEEE Transactions on Computers · 2000 · 118 citations
An Algorithm for Exact Division
Tudor Jebelean · Journal of Symbolic Computation · 1993 · 59 citations