The paper presents 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 car
ry save adder. Given the (n + k)-bit X and the n-bit M the modular red
uction algorithm computes the n-bit residue R in O(k + log n) time, an
d is particularly useful when the operand size is large. We also prese
nt a variant of the algorithm that performs modular multiplication by
interleaving the shift-and-add and the modular reduction steps. The mo
dular multiplication algorithm can be used to obtain efficient VLSI im
plementations of exponentiation cryptosystems.