Multiplication in prime fields with large unstructured primes is a fundamental building block of modern cryptography. Modular multiplication of two field elements a,b∈Fₚ requires computing their full product ab and reducing it modulo p. The two most widely used reduction algorithms are due to Barrett and Montgomery, with the latter operating in a permuted coset of the field (Montgomery form).
Single-precision implementations of both algorithms typically require three full multiplications: one for ab and two for the reduction. With schoolbook multiplication, each full multiplier costs n² digit multiplications, resulting in a total of 2n² for the reduction. Faster methods like Karatsuba can decrease the number of digit multiplications but introduce significant overhead in additions and complex internal dependencies, making them less suitable for CPU-based implementations.
Multi-precision approaches (operand scanning), particularly with Montgomery reduction, are the most widely used today. The best known algorithm (at least to us and ChatGPT) achieves reduction in n²+n digit multiplications without increasing additions or introducing complex dependencies, making it highly efficient for CPU-based systems.
In this note, we aim to explore modular reduction from a fresh perspective, balancing conciseness with an informal approach. Specifically, let us:
- Introduce an alternative way to conceptualize modular reduction, revealing a natural duality between Barrett and Montgomery methods.
- Present the n²+n Montgomery reduction algorithm.
- Derive the dual n²+n Barrett reduction counterpart.
- Explain why Montgomery reduction is inherently better suited for CPU-based implementations.
- Introduce a new n²+1 algorithm, demonstrating its applicability to both Montgomery and Barrett reductions.
- Show how Barrett and Montgomery reductions can often be used interchangeably in key cryptographic primitives.
As far as we are aware, much of this content is novel, providing new insights into the structure and efficiency of modular reduction techniques.
Read the full technical note on HackMD.
