TABLE OF CONTENTS 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 = ? a/ b ?. The result r is said to be "congruent to a modulo b," which is also written as r ? a (mod b). In other vernacular, r is known as the "modular residue," which leads to "quadratic residue" [1] and other forms of residues.
Modular reductions are normally used to create finite groups, rings, or fields. The most common usage for performance driven modular reductions is in modular exponentiation algorithms; that is, to compute d = a b (mod c) as fast as possible. This operation is used in the RSA and Diffie-Hellman public key algorithms, for example. Modular multiplication and squaring also appears as a fundamental operation in elliptic curve cryptographic algorithms. As will be discussed in the subsequent chapter, there exist fast algorithms for computing modular exponentiations without having to perform ( in this example) b -
