Verified Newton-Raphson Iteration for Multiplicative Inverses Modulo Powers of Any Base

摘要

We identify two faults in a published algorithm for fast computation of multiplicative inverses modulo prime powers. We patch the algorithm and present machine-assisted proofs of correctness of the repair. Our formal proofs also reveal that being prime is an unnecessary demand for the power base, thus attributing a wider scope of applications to the repaired algorithm.