You are looking at a specific version 20170513:153305 of this paper.
See the latest version.
Paper 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}$.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- Inversion mod pmod p^kand 2^k
- Contact author(s)
- koc @ cs ucsb edu
- History
- 2017-06-28: last of 2 revisions
- 2017-05-13: received
- See all versions
- Short URL
- https://ia.cr/2017/411
- License
-
CC BY