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

Jeffrey Hurchalla · 2022 · arXiv cs.DS

| 编号 QM023 | 主题 模运算与乘法 | 链接 arXiv:2204.04342 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

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.

适用范围

本文是纯经典算法，且模数限定为 $2^w$（整数寄存器宽度）。它可以作为量子求逆线路的经典算法学基础，但不是 Shor 求逆所需的模乘逆元量子线路。

本站词条在引用该文献时，会以 wikilink（sources/QM023）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。