Patent ID: 7480691

Claim:
An arithmetic circuit which performs a multiplication of a multiplicand A and a multiplier B expressed by bit patterns, comprising: a partial product generation circuit to generate a plurality of partial products in a secondary Booth algorithm from the multiplicand A; an encoder circuit to encode the multiplier B based on the secondary Booth algorithm, and output a selection signal depending on a value of i specifying three consecutive bits b 2i+1 , b 2i , and b 2i−1 of the multiplier B specified by the value of i; a selection circuit to select and output one of the plurality of partial products according to the selection signal; an addition circuit to add up partial products specified by the value of i output from the selection circuit, and generate a multiplication result; and a storage storing the result used for cryptography, and wherein said arithmetic device has an operation mode in which said encoder circuit outputs a selection signal for selection of a partial product indicating −A when i is 0, and outputs a selection signal for selection of a partial product indicating 0 when i is a value other than 0, and said addition circuit generates a two's complement of the multiplicand A from the partial product indicating A, and outputs the two's complement of the multiplicand A as the result.