**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 algorithm given by
Dussé and Kaliski for computing $a^{-1}\pmod{2^k}$.

**Category / Keywords: **implementation / Inversion mod p, mod p^k, and 2^k

**Date: **received 11 May 2017

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

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

**Version: **20170513:153305 (All versions of this report)

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

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

[ Cryptology ePrint archive ]