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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/411}},
      url = {https://eprint.iacr.org/2017/411}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.