论文标题
改进的整数模块化乘数倒数（Modulo $ 2^W $）
An Improved Integer Modular Multiplicative Inverse (modulo $2^w$)
论文作者
论文摘要
本文提出了一种用于整数乘法逆（mod $ 2^w $）的算法，该算法以现代微处理器闻名的最少的周期完成，当时使用本机位宽度$ W $用于模量$ 2^w $。该算法是DUMA对方法的修改，对于计算机而言，它略有提高通用性和效率。给出了证明，并且该算法与逆向的牛顿的方法算法密切相关。该算法和牛顿方法所需的简单直接公式对整数逆模量$ 2^k $进行了审查和证明，$ k $ = 1、2、3、4或5，提供了$ k $ $ = 4或5的首选公式的第一个证明。
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.
