**A New Algorithm for Inversion mod $p^k$**

*Çetin Kaya Koç*

**Abstract: **A new algorithm for computing $x=a^{-1}\pmod{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}\pmod{p}$ and iteratively computes the digits of
the inverse $x=a^{-1}\pmod{p^k}$ in base $p$.
The mod 2 version of the algorithm is significantly more
efficient than the existing algorithms for small values
of $k$. 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 $p$, any $k$, and digit-by-digit. Moreover it requires
the minimal number of arithmetic operations (just a single
addition) per step.

**Category / Keywords: **number theory, arithmetic, cryptography

**Date: **received 11 May 2017, last revised 28 Jun 2017

**Contact author: **koc at cs ucsb edu

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20170628:154617 (All versions of this report)

**Short URL: **ia.cr/2017/411

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]