Patent ID: 8977668
Filing Date: 2015-03-10
Classification: G06F

Abstract:
1. A device for calculating a result of a modular multiplication with a multiplier, a multiplicand and a modulus, comprising: a unit for providing the multiplicand in at least three portions, wherein each portion comprises a number of digits less than half the number of digits of the multiplicand, and wherein the at least three portions include all digits of the multiplicand; and a sequential calculator circuit, wherein the sequential calculator circuit is formed to calculate a first intermediate result using a more significant portion of the multiplicand, to calculate a second intermediate result using a less significant portion of the multiplicand and the first intermediate result, and to calculate and store a third intermediate result using a still less significant portion of the multiplicand and the second intermediate result, wherein the third intermediate result represents the result of the modular multiplication, if the multiplicand is divided into exactly three portions, or wherein the result of the modular multiplication is derivable from the third intermediate result by a further sequential calculation, if the multiplicand is divided into more than three portions, wherein the sequential calculator circuit comprises a calculating unit for reducing an input number with respect to a modulus, wherein the input number comprises input number portions of different significances, wherein the input number portions represent the input number with respect to a division number, wherein the modulus comprises modulus portions of different significances, and wherein the modulus portions represent the modulus with respect to the division number, the calculating unit 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 circuit 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.