An Improved Integer Modular Multiplicative Inverse (modulo 2^w)

2022/04/09 by Jeffrey Hurchalla, Hurchalla, Jeffrey · 1 citation
Computer Science · #Numerical Methods and Algorithms #Digital Filter Design and Implementation #Cryptography and Residue Arithmetic

paper · pdf · doi:10.48550/arxiv.2204.04342

Abstract

This paper presents an algorithm for the integer multiplicative inverse (mod 2^w) which completes in the fewest cycles known for modern microprocessors, when using the native bit width w for the modulus 2^w. The algorithm is a modification of a method by Dumas, and for computers it slightly increases generality and efficiency. A proof is given, and the algorithm is shown to be closely related to the better known Newton's method algorithm for the inverse. Simple direct formulas, which are needed by this algorithm and by Newton's method, are reviewed and proven for the integer inverse modulo 2^k with k = 1, 2, 3, 4, or 5, providing the first proof of the preferred formula with k=4 or 5.

Cited by

• On the Inversion Modulo a Power of an Integer

Related

• On the Inversion Modulo a Power of an Integer
• Modular Inverses and Chinese Remainder Algorithm
• Semi-primitive roots and the discrete logarithm module 2^k
• Memory Efficient Arithmetic
• Modular Inverse and Reciprocity Formula