Method and apparatus for calculating the remainder of a modulo division

摘要

A non-iterative technique for calculating the remainder of modulo division, which requires significantly fewer operations than the traditional iterative technique for the same calculation. The number of calculations required in the present invention is independent of the number of bits of the divisor in the modulo operation. Two requirements of the non-iterative technique are that the value of the divisor D should be equal to 2ⁿ-1 (where n is the number of bits of the divisor D) and the value of the dividend N should be less than or equal to (D-1)², but greater than or equal to zero. If these two conditions are met, the remainder R of N mod D is determined by summing the up