Cryptology ePrint Archive: Report 2017/411

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 ]