tailieunhanh - A Fast Algorithm for Modular Reduction

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. | A Fast Algorithm for Modular Reduction C. K. Kog t Electrical and Computer Engineering Oregon State University Corvallis Oregon 97331 USA C. Y. Hung DSP R D Center Texas Instruments Inc. Dallas Texas 75265 USA 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 logn 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. Key Words Carry save adder sign estimation technique division modular multiplication. 1 Introduction Arithmetic operations with long operands are often carried out using redundant representations in order to avoid a full-length carry propagation delay. In the modular reduction operation X mod M we need to compare X with some integer multiple q of M or equivalently calculate the sign of X qM . However in a redundant representation the sign of a number may not be readily available. In particular when the carry save addition technique is used the precise determination of the sign of an n-bit number represented by a carry-sum pair requires the computation of the total sum which takes O n time with a carry propagate adder. We present an improved version of the sign estimation technique 13 for detecting the sign of a number represented in the form of a carry-sum pair. The sign estimation technique was used to obtain fast algorithms for multi-operand modular addition 13 and modular multiplication 12 14 operations. The improved sign estimation algorithm presented here correctly computes the sign of the number .