Modular Reduction

Presentation: https://youtu.be/2vC5fDOdYck

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 , which is inefficient, not scalable, and difficult to implement in hardware architecture. The most popular workaround uses or reduction based multiplication algorithm. There is also some specialized multiplication algorithms like Karatsuba-Barrett Algorithm etc.

PreviousModular Arithmetic NextBarrett Reduction

Last updated 1 month ago

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}