On the Inversion Modulo a Power of an Integer

This paper presents two generalized algorithms for efficiently computing modular inverses modulo $n^k$ and $n^{2^s}$ for any integer $n>1$, extending previous prime-power methods to leverage computer architecture and improve computational performance.

The Gist

Imagine you are trying to unlock a very special, high-security safe. The combination to this safe is a number called a modular inverse. In the world of cryptography (the math behind secure internet connections), finding this combination is a daily task.

Usually, finding this combination is like trying to solve a maze by walking backward from the exit. It's slow, and if the maze gets bigger (the numbers get larger), it takes forever.

This paper introduces two new, clever ways to solve this maze much faster. The authors, Guangwu Xu, Yunxiao Tian, and Bingxin Yang, are like master locksmiths who have found shortcuts that work not just for one type of lock, but for almost any kind.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Division" Bottleneck

In math, finding an inverse is essentially the opposite of multiplication. Usually, to reverse multiplication, you have to do division.

• The Analogy: Imagine you are baking a cake. Multiplication is easy: you mix ingredients. Division is hard: you have to un-mix them, separating the flour from the eggs. Computers are great at mixing (multiplying) but terrible at un-mixing (dividing).
• The Goal: The authors want to find a way to "un-mix" the cake using only the easy tools (addition and shifting digits) instead of the hard tool (division).

2. Part One: The "Schoolbook" Shortcut

The first major contribution is a new algorithm that works for any number base, not just the special ones computers usually like (like powers of 2).

• The Old Way (Koç's Algorithm): Previously, a method existed, but it was like a specialized tool that only worked on locks made of prime numbers (like 2, 3, 5, 7). It was fast, but limited.
• The New Way (The Schoolbook Method): The authors looked at how we learned to multiply numbers in elementary school. Remember how we multiplied big numbers by breaking them down into digits and carrying over the "leftovers"?
  • The Analogy: They realized that finding the inverse is just like doing that schoolbook multiplication in reverse. Instead of carrying over numbers to the left, they "carry" the error to the right.
  • The Magic: By using the computer's built-in ability to handle huge chunks of data at once (like 64-bit or 128-bit chunks), they can solve the puzzle in giant leaps rather than tiny steps.
  • The Result: They tested this on modern computers. When they used a "base" of $2^{64}$(a standard computer word size) or even$2^{128}$, their method was dramatically faster than the old methods. It's like switching from walking to a high-speed train.

3. Part Two: The "Hensel Lifting" Upgrade

The second part of the paper deals with a specific type of lock where the modulus is a power of a prime number (like $2^s$). There were already some fast methods for this, developed by researchers named Dumas and Hurchalla.

• The Analogy: Imagine you are climbing a ladder. The old methods were like climbing one rung at a time, or maybe two rungs at a time.
• The Innovation: The authors took these existing "ladder-climbing" methods and generalized them. They showed that you don't need the ladder to be made of a specific material (a prime number). You can climb a ladder made of any integer.
• The Math Trick: They used a simple algebraic trick (like a magic formula) to show that the same "jumping" logic used for prime numbers works for any number $n$. This makes the fast "Hurchalla" method available to everyone, not just those working with prime numbers.

4. Why Does This Matter?

You might ask, "Who cares about finding the inverse of a number?"

• Real-World Impact: This math is the engine behind encryption. Every time you visit a secure website (https), send a private message, or use a digital signature, your computer is doing millions of these calculations.
• The Benefit: If the calculation is faster, your internet is faster, your battery lasts longer, and your devices can handle more complex security without slowing down.
• The Future: As we move toward "Post-Quantum" cryptography (security that can't be broken by future quantum computers), these calculations will become even more critical. This paper provides the tools to make those future systems run efficiently today.

Summary

Think of this paper as a universal toolkit for digital locksmiths.

1. Tool 1: A new, flexible method based on elementary school math that works on any number base, making it incredibly fast on modern computers.
2. Tool 2: An upgrade to existing fast methods, proving they work for any number, not just special prime ones.

The authors didn't just find a slightly better way to do the math; they found a way to make the "un-mixing" of numbers as easy and fast as the "mixing," which is a huge win for the speed of our digital world.

Technical Summary

Here is a detailed technical summary of the paper "On the Inversion Modulo a Power of an Integer" by Xu, Tian, and Yang.

1. Problem Statement

The paper addresses the computational problem of finding the modular multiplicative inverse $x = a^{-1} \pmod{m}$, specifically where the modulus $m$ is a power of an integer ($n^k$ or $n^{2s}$).

• Context: Modular inversion is a bottleneck in cryptography (RSA, ECC, post-quantum schemes) and homomorphic encryption.
• Limitations of Existing Methods:
  • General Case: Standard methods (Extended Euclidean Algorithm) are computationally expensive.
  • Prime Powers ($p^k$): Ko¸c proposed an efficient algorithm for prime powers using $p$-adic expansions, but it is restricted to prime bases.
  • Special Powers ($p^{2s}$): Dumas and Hurchalla developed efficient Hensel lifting methods for $p^{2s}$ (particularly $2^w$), but these are also restricted to prime bases.
  • Arbitrary Bases: There was a lack of efficient, general algorithms for moduli of the form $n^k$ where $n$ is an arbitrary integer (not necessarily prime), such as $n=10$ (decimal) or $n=2^{64}$ (computer word size).

2. Methodology

The authors propose two distinct algorithmic approaches to generalize existing methods:

Part A: Generalization of Ko¸c's Algorithm (Schoolbook Multiplication Approach)

• Core Concept: The authors derive a new algorithm for computing $a^{-1} \pmod{n^k}$ for any integer $n > 1$ and $k > 0$.
• Motivation: The algorithm is inspired by schoolbook multiplication. By analyzing the carry propagation when multiplying $a \times x$ (where $x$ is the inverse) in base $n$, the authors derive a recurrence relation.
• Mechanism:
  • Let $x = X_0 + X_1n + \dots + X_{k-1}n^{k-1}$.
  • The algorithm computes digits $X_i$ iteratively.
  • It utilizes a state variable $T_i$ representing the "carry" or residual error.
  • Recurrence: $T_{i} = T_{i-1} + X_{i-1}a$ (divided by $n$), and $X_i = -c \cdot T_i \pmod n$, where $c = a^{-1} \pmod n$.
• Key Feature: The algorithm relies primarily on addition, subtraction, and right-shifting (division by $n$). If $n$ is a power of 2 (e.g., $2^{64}$), the division becomes a trivial bit-shift, leveraging native CPU arithmetic.

Part B: Generalization of Hensel Lifting (Dumas/Hurchalla Approach)

• Core Concept: The authors generalize the Hensel lifting method used by Dumas and Hurchalla, which was previously limited to moduli of the form $p^{2s}$ (prime base).
• Mechanism:
  • They provide a simple algebraic derivation to extend the recurrence to moduli of the form $n^{2s}$ for any integer $n > 1$.
  • Initialization: Compute an initial approximation $x_0 = a^{-1} \pmod{n^{2h_0}}$.
  • Recurrence: Define $y = 1 - ax_0 \pmod{n^{2s}}$. The sequence is updated via $x_{m+1} = x_m(1 + y^{2^m}) \pmod{n^{2s}}$.
  • This effectively doubles the precision of the inverse in each step (divide-and-conquer strategy).
• New Contribution: The paper also derives a new explicit formula for the initial approximation $x_0$ when working modulo $2^5$(and by extension$2^4$), utilizing bitwise XOR operations on specific bits of$a$.

3. Key Contributions

1. Algorithm for Arbitrary Moduli ($n^k$): The first efficient algorithm to compute modular inverses for $a^{-1} \pmod{n^k}$ where $n$ is any integer $>1$, not just a prime.
2. Optimization for Native Word Sizes: By setting $n = 2^{64}$ or $n = 2^{128}$, the algorithm fully utilizes the 64-bit or 128-bit arithmetic capabilities of modern CPUs. This avoids expensive multi-precision division, replacing it with fast shifts and additions.
3. Generalized Hensel Lifting: Extending the $p^{2s}$ Hensel lifting methods to $n^{2s}$, making them applicable to composite bases.
4. Alternative Proof of Ko¸c's Algorithm: The paper provides a novel proof of correctness for Ko¸c's algorithm, revealing that the algorithm simultaneously computes $(p^s)^{-1} \pmod a$ as a byproduct.
5. New Bitwise Initialization: A specific formula for initializing the Hensel lifting process for $2^5$ using bitwise operations.

4. Experimental Results

The authors implemented their algorithms (specifically Algorithm 3.1 with $n=2^{64}$ and $n=2^{128}$) and compared them against:

• Ko¸c's binary algorithm (Algorithm 2.2).
• Hurchalla's algorithm (from [7]).
• Hardware: AMD Ryzen 7 8845HS, Ubuntu 24.04, GCC 14.2.0 with -Ofast -march=native.

Performance Findings:

• Significant Speedup: The proposed algorithm is drastically faster than existing methods, especially for large bit lengths ($k$).
• Comparison Data (Average runtime in nanoseconds for $a^{-1} \pmod{2^k}$):
  • At $k=256$ bits:
    • Proposed ($n=2^{64}$): 22.27 ns
    • Proposed ($n=2^{128}$): 17.71 ns
    • Hurchalla: 164.48 ns
    • Ko¸c: 5546.50 ns
  • At $k=4096$ bits:
    • Proposed ($n=2^{128}$): 4989.27 ns
    • Hurchalla: 26724.95 ns
    • Ko¸c: 389627.86 ns
• Observation: Using a larger radix ($n=2^{128}$) often outperforms $n=2^{64}$ for very large moduli, as it reduces the number of iterations required.

5. Significance

• Cryptographic Efficiency: The results offer a substantial reduction in computational overhead for modular inversion, a critical operation in public-key cryptography and post-quantum schemes.
• Hardware Alignment: The approach aligns perfectly with modern computer architecture (64-bit/128-bit word sizes), maximizing throughput by minimizing complex arithmetic operations.
• Theoretical Unification: The paper unifies the understanding of modular inversion across prime and composite bases, showing that "schoolbook" logic and Hensel lifting can be generalized beyond prime fields.
• Practical Applicability: The ability to handle non-prime bases (like $n=10$ for decimal systems or $n=2^{64}$ for binary systems) makes these algorithms versatile for various digital arithmetic applications.