Patent ID: 8176109

Claim:
A calculating unit for reducing an input number with respect to a modulus, wherein the input number comprises input number portions of different significances, the input number portions represent the input number with respect to a division number, the modulus comprises modulus portions of different significances, and the modulus portions represent the modulus with respect to the division number, comprising: a unit for estimating a result of an integer division of the input number by the modulus using a stored most significant portion of the input number, using a stored most significant portion of the modulus and using the division number, and for storing the estimated result or an estimated value derived from the estimated result in a memory of the calculating unit; and a reduction result calculator configured for calculating a reduction result based on a result of a subtraction of a product of the modulus and the estimated result from the input number or based on a result of a subtraction of a product of the modulus and the estimated value from the input number, wherein the unit for estimating is formed to evaluate the following equation: ( {tilde over (Q)} 0 ,{tilde over (R)} 0 ):=MMD( D 3 ,Z−N 2 ;N 2 ), wherein {tilde over (Q)} 0 is a result of an integer division, {tilde over (R)} 0 is an integer remainder of the integer division, MMD is a Mult-Mod-Div operation D 3 is the most significant portion of the input number Z is the division number, and N 2 is the most significant portion of the modulus.