On Calculating Multiplicative Inverses Modulo $2^{m}$

O. Arazi, Hairong Qi

IEEE Transactions on Computers · 2008 · 16 citations · 6 references

Concepts

Abstract

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.

References

6