Welcome to the resource topic for 2017/411
Title:
A New Algorithm for Inversion mod p^k
Authors: Ç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.
ePrint: https://eprint.iacr.org/2017/411
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .