Patent ID: 6668267
Filing Date: 2003-12-23
Classification: G06F

Abstract:
An integrated circuit comprising a modular arithmetic coprocessor comprising:storage means to store and serially provide a first operand A and a second operand B, a modulo N and a result S, A being an integer encoded on a*k bits, with a being a non-zero integer at most equal to m, and B, N and S being integers encoded on at most m*k bits, and with m and k being integers greater than 1; and computation means to perform modular operations according to the Montgomery method and comprising a first k-bit latch to store a k-bit word Ai of the first operand A, a second k-bit latch to store either a least significant word of N or an intermediate data element Y0 encoded on k bits such that Y0=((S(iâˆ’1)+(Ai*B))*J0) mod 2k, i being a loop index varying from 0 to aâˆ’1, S(iâˆ’1) being an updated result of S during the (iâˆ’1)th iteration, S(âˆ’1) being equal to zero, Ai being an ith k-bit word of the first operand A, and J0 being a k-bit word resolving equation ((J0*N)+1) mod 2k=0, addition means to add contents of the first and second latches, selection means coupled to outputs of the first and second latches and to the addition means to give, at a parallel output, either the word contained in the first latch, the word contained in the second latch, a sum of the words contained in the first and second latches, or a word zero as a function of a bit of the second operand B and of a bit of the modalo N, an accumulator circuit that adds, shifts by one bit and stores the words given successively by the selection means with one bit of an updated result, a bit output from the accumulator circuit becoming a new updated result, and a circuit to compute an intermediate data element Y0 connected, first, to the output of the second latch to receive the least significant k-bit word of the module N and, second, to the output of the accumulator circuit to receive a data element X=S(iâˆ’1)+Ai+B.