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 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.
Note: Small improvements in the paper. This is the final version.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- number theoryarithmeticcryptography
- 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
BibTeX
@misc{cryptoeprint:2017/411,
author = {Çetin Kaya Koç},
title = {A New Algorithm for Inversion mod $p^k$},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/411},
year = {2017},
url = {https://eprint.iacr.org/2017/411}
}
