Paper 2017/411

A New Algorithm for Inversion mod $p^k$

Çetin Kaya Koç

Abstract

A new algorithm for computing $x=a^{-1}(\mathrm{mod}{p}^k)$ is introduced. It is based on the exact solution of linear equations using $p$-adic expansions. It starts with the initial value $c=a^{-1}(\mathrm{mod}p)$ and iteratively computes the digits of the inverse $x=a^{-1}(\mathrm{mod}{p}^k)$ in base $p$. The mod 2 version of the algorithm is significantly more efficient than the existing algorithms for small values of $$. We also describe and analyze all existing algorithms, and compare them to the proposed algorithm. Our algorithm stands out as being the only one that works for any $$, any $$, and digit-by-digit. Moreover it requires the minimal number of arithmetic operations (just a single addition) per step.

Note: Small improvements in the paper. This is the final version.