Fast Algorithm for Modular Reduction

C. K. Koc and C. Y. Hung

IEE Proceedings - Computers and Digital Techniques, 145(4):265-271, July 1998.

Abstract

We present an algorithm for computing the residue R = X mod M. The algorithm is based on a sign estimation technique that estimates the sign of a number represented by a carry-sum pair produced by a carry save adder. Given the (n+k)-bit X and the n-bit M, the modular reduction algorithm computes the n-bit residue R in O(k+log(n)) time, and is particularly useful when the operand size is large. We also present a variant of the algorithm that performs modular multiplication by interleaving the shift-and-add and the modular reduction steps. The modular multiplication algorithm can be used to obtain efficient VLSI implementations of exponentiation cryptosystems.