At the heart of modern cryptography lies a deceptively simple mathematical operation: modular multiplication ($A \times B \pmod p$). Whether executing classical protocols like RSA and Elliptic Curve Cryptography (ECC), or deploying post-quantum cryptography (PQC) standards like CRYSTALS-Kyber, hardware and software must compute these residues millions of times per second.
The fundamental bottleneck is the modulo operation itself. Standard division requires iterative subtraction and comparison, an inherently sequential process that is notoriously expensive in silicon and software alike. To achieve high throughput on everything from high-performance GPUs to ultra-low-power IoT microcontrollers, researchers have developed a suite of techniques designed to bypass division entirely.
By transforming how numbers are represented, delaying reductions until absolutely necessary, and choosing mathematically cooperative prime moduli, modern implementations turn expensive division into cheap bitwise shifts and additions.
Radix Transformation: Making Division "Free"
The most intuitive way to avoid dividing by an awkward prime $p$ is to change the number system so that you divide by a number that is "free" to divide by: a power of two ($2^k$). In a binary system, dividing by $2^k$ is simply a right shift by $k$ bits, and taking the remainder is a bitwise AND operation.
Montgomery and Barrett reduction are classic examples of this strategy. By mapping operands into a transformed radix domain, standard division is replaced by a few low-precision multiplications and bit-shifts. For instance, Chu et al. leveraged Montgomery reduction on GPUs to accelerate homomorphic hash functions, demonstrating how offloading these bitwise shifts and multiplications removes the computational bottlenecks of high-precision arithmetic on parallel architectures. To maximize performance, Seo et al. showed that separating the multiplication phase from the modular reduction phase allows developers to optimize parallelized multiplication routines independently before handling the residue.
However, standard Montgomery reduction can introduce high register pressure because it requires keeping track of multiple wide intermediate products. This is a critical issue on modern 64-bit architectures. To solve this, Ji et al. utilized Plantard arithmetic, an alternative framework that requires fewer multiplication instructions and registers. By minimizing register pressure, more intermediate values can reside directly within the CPU, preventing performance-degrading memory spills.
On low-end 32-bit IoT devices lacking SIMD extensions, Huang et al. refined Plantard arithmetic to support a significantly larger input range. This mathematical flexibility allowed the authors to exploit platform-specific hardware features—such as inline barrel shifters—to merge shifts and additions into single clock cycles, compensating for the lack of specialized vector hardware.
Standard Modular Reduction:
[A × B] ---> [ Divide by Prime p ] ---> Slow Iterative Subtractions
Radix-Transformed Reduction (e.g., Montgomery/Plantard):
[A × B] ---> [ Transform Modulo ] ---> [ Bitwise Right Shift (>> k) ] ---> Fast Bitwise Operations
Lazy Reduction: Exploiting Register Slack
When computing complex cryptographic transforms—such as the Number Theoretic Transform (NTT) used in lattice-based cryptography—hardware must perform long chains of multiply-accumulate operations ($A \cdot B + C \cdot D + \dots$). Reducing the result modulo $p$ after every single operation is highly redundant.
Lazy reduction is the practice of intentionally deferring modular reduction. If a processor register is 32 or 64 bits wide, but the cryptographic modulus $p$ is only 12 bits wide (as in Kyber), the product of two numbers fits comfortably within the register with room to spare. This "register slack" allows intermediate values to accumulate over multiple operations without overflowing.
Eager Reduction: (A × B mod p) + (C × D mod p) + (E × F mod p) --> 3 expensive reductions
Lazy Reduction: (A × B + C × D + E × F) mod p --> 1 single deferred reduction
Azarderakhsh et al. demonstrated the power of this approach in Ring-LWE encryption, showing that delaying modular reduction until strictly necessary drastically lowers the instruction count by eliminating redundant subtraction cycles.
To maximize the efficiency of lazy reduction, Huang et al. designed modular reduction algorithms that natively support signed integer inputs and outputs. By allowing negative values to be processed directly within the arithmetic logic, the authors eliminated the need for extra normalization steps during the butterfly operations of the NTT, significantly streamlining the execution pipeline.
Structural Moduli: Replacing Multipliers with Shifts
On hardware platforms like FPGAs or ultra-low-power microcontrollers, specialized Digital Signal Processing (DSP) slices and hardware multipliers are scarce, power-hungry resources. The ultimate optimization is to eliminate multipliers entirely, achieving multiplier-less modular reduction.
This becomes possible when designers have the freedom to choose a "hardware-friendly" modulus $p$. If a prime is chosen such that it can be expressed as a small number of signed powers-of-two (e.g., $p = 2^a \pm 2^b \pm 1$), the reduction logic can be hardwired using nothing but bit-shifters and adders.
Tan et al. leveraged this concept by selecting specific moduli compatible with both the Chinese Remainder Theorem and the NTT that decompose into a few signed powers-of-two. This allowed them to build dedicated hardware units composed entirely of bit-shifters and adders, offloading arithmetic complexity from specialized DSPs to general logic gates and drastically reducing the hardware area-time product. Similarly, Kuo et al. applied a sequence of bit-shifts and additions to implement highly efficient hardware reduction for the NewHope protocol on FPGAs.
This structural optimization is equally potent in software for highly constrained architectures. On 8-bit AVR microcontrollers, Chu et al. and Chu et al. utilized "Optimal Prime Fields" where the prime is structured as $p = u \cdot 2^k + v$. Because the byte-level representation of these primes consists mostly of zeros, the number of non-zero byte operations required during reduction drops precipitously, allowing 8-bit devices to perform high-security elliptic curve scalar multiplications with minimal energy consumption.
For broader applications where primes cannot be chosen arbitrarily, algorithmic variants still mimic this behavior. Li introduced the Shift-Sub Modular Multiplication (SSMM) algorithm, which uses Carry-Save Adders (CSAs) and bit-shifts to perform modular multiplication iteratively without standard multipliers, striking a favorable balance between clock frequency and silicon area.
Algorithmic Simplifications
When the modulus cannot be perfectly expressed as a power of two, algebraic identities can still be exploited to minimize intermediate bit-widths. For example, Liu et al. utilized the algebraic property:
$$(p - A)(p - B) \equiv AB \pmod p$$
By transforming operands using this identity, they eliminated the expensive higher-order terms that typically arise when squaring large numbers. Furthermore, the authors showed that for primes that sit exactly adjacent to highly composite numbers, modular reduction can be compressed into a single division followed by a quick conditional correction step, bypassing the iterative loops of standard reduction algorithms.
By pairing these algebraic shortcuts with refined reduction frameworks—such as the optimized Barrett reduction developed by Tian et al. to minimize intermediate bit-widths—modern cryptographic engineering successfully transforms the theoretical bottleneck of modular division into a highly parallelizable, low-overhead sequence of simple additions and shifts.
Key Foundational Work
Practical Random Linear Network Coding on GPUs (2009) — contributed 1 concept elements to this direction.
Multi-modular algorithm for computing the splitting field of a polynomial (2008) — contributed 1 concept elements to this direction.