Patent ID: 8291223
Filing Date: 2012-10-16
Classification: G06F

Abstract:
1. An arithmetic circuit for performing Montgomery multiplication, comprising: a sum-of-products calculation circuit adapted to execute a sum-of-products calculation process to accept first, second, third and fourth variables of a bit width r, and calculate a sum of the third variable, a product of the first and second variables, and the fourth variable thereby to output calculation result data of a bit width 2r; a first memory configured by a synchronous one-port RAM having a storage area for storing an intermediate result storage array of a bit width r with a number s of elements, and adapted to output each element of the intermediate result storage array as the third variable to the sum-of-products calculation circuit; a second memory configured by a synchronous one-port RAM having a storage area for storing first and second arrays of a bit width r with a number s of elements, and adapted to output each element of the first array as the first variable to the sum-of-products calculation circuit; a multiplicand storage register adapted to accept and store the second array from the second memory in units of element, and output each element of the second array as the second variable to the sum-of-products calculation circuit; and a carry register adapted to accept and store most significant bit-side data including most significant r bits of the calculation result data, and output the most significant bit-side data as the fourth variable to the sum-of-products calculation circuit, the arithmetic circuit executing: a first read process for reading the elements of the second array indicated by a predetermined first loop counter value from the second memory, and storing the elements in the multiplicand storage register; a second read process for reading the elements of the first array indicated by a predetermined second loop counter value from the second memory, the elements of the intermediate result storage array indicated by the second loop counter value from the first memory, a value of the multiplicand storage register and a value of the carry register, and inputting each of the read out elements and values to the sum-of-products calculation circuit; and a write process for writing the most significant bit-side data in the carry register and least significant bit-side data including least significant r bits of the calculation result data in the first memory as the elements of the intermediate result storage array indicated by the second loop counter value, wherein the first read process is followed by a first subloop process for repeatedly executing the second read process, the sum-of-products calculation process, the write process and a process of updating the second loop counter value.