Algorithms for Inversion Mod pk

Çetin Kaya Koç

doi:10.1109/TC.2020.2970411

Return

Algorithms for Inversion Mod pk

2020-06-01

PRE

Çetin Kaya Koç *

DOI：10.1109/TC.2020.2970411

Original

Original request for help

Save

Abstract

En 中文

This article describes and analyzes all existing algorithms for computing x = a(-1) omod pk THORN for a prime p, and also introduces a new algorithm based on the exact solution of linear equations using p-adic expansions. The algorithm starts with the initial value c = a(-1) omod pTHORN and iteratively computes the digits of the inverse x = a(-1) omod pk THORN in base p. The mod 2 version of the algorithm is more efficient than all existing algorithms for small values of k. Moreover, it stands out as being the only one that works for any p, any k, and digit-by-digit. While the new algorithm is asymptotically worse off, it requires the minimal number of arithmetic operations (just a single addition) per step, as compared to all existing algorithms.

Keywords:

Number-theoretic algorithms

computer arithmetic

multiplicative inverse

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.