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.sup.n-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).sup.2, 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 upper ##EQU00001## and lower ##EQU00002## bits of the dividend N.
Generation a remainder from a division of a first polynomial by a second polynomial having a variable width. One or more embodiments include a first sub-circuit, a first adder, a second sub-circuit, and a second adder. The first sub-circuit is adapted to generate a first partial remainder, which has a fixed width greater than or equal to the width of the second polynomial, from the first polynomial excepting a least significant portion. The first adder is adapted to generate a sum of the least significant portion of the first polynomial and a most significant portion of the first partial remainder. The second sub-circuit is adapted to generate a second partial remainder from the sum. The second adder is adapted to generate the remainder from the second partial remainder and the first partial remainder excepting the most significant portion.
A device for converting a term comprising a product of a first operand and a second operand into a representation having an integer quotient regarding a modulus and a remainder, the integer quotient being defined by T/N, T being the term and N being the modulus, and the remainder being defined by T mod N, N being the modulus. The device modularly reduces the term using the modulus on the one hand and modularly reduces the term using an auxiliary modulus, which is greater than the modulus, on the other hand to obtain the remainder on the one hand and the auxiliary remainder on the other hand. Both the remainder and the auxiliary remainder are combined to obtain the integer quotient. The inventive device makes it possible to calculate even the integer quotient, that is the result of the divide (DIV) operation, by performing a command for a modular multiplication existing on conventional cryptoprocessors two times.
