BigNum Math

Chapter 6

Modular Reduction

6.1 Basics of Modular Reduction

Modular reduction arises quite often within public key cryptography algorithms and various number theoretic algorithms, such as factoring. Modular reduction algorithms are the third class of algorithms of the “multipliers” set. A number a is said to be reduced modulo another number b by finding the remainder of the division a/b. Full integer division with remainder is covered in Section 8.1.

Modular reduction is equivalent to solving for r in the following equation: a= bq+ r where q= . The result r is said to be “congruent to a modulo b,” which is also written as r≡a(mod b). In other ...