Modular Reduction

Introduction

To calculate modular addition, $(A+B) \mod q$, we can simply use a piecewise function:

$$(A + B) \mod q = \begin{cases} A + B &\text{if }A + B < q \\ A + B − q &\text{if }A + B ≥ q \end{cases}$$

While modular adder is simple and easy to implement, modular multipliers are trickier. The standard algorithm for modular multiplication uses trial division, which is inefficient, not scalable, and difficult to implement in hardware architecture. The most popular workaround uses Barrett or Montgomery reduction based multiplication algorithm. There is also some specialized multiplication algorithms like Karatsuba-Barrett Algorithm etc.