Patent ID: 8631249

Claim:
An operation unit that generates a pre-calculated table C′ including (4×2 b/2 ) pieces of b-bit element data C′[y] individually readable by (4×2 b/2 ) indices y (0≦y<4×2 b/2 ) before processing to obtain an addition result of upper (k−1)b bits by adding a kb-bit number A composed of a number A 1 of upper (k−1)b bits and a number A 2 of lower b bits (b>4) and a number r of b bits and can propagate carrying-over from the addition result of the number A 2 and the number r to the number A 1 based on the pre-calculated table C′ during the processing of the addition, comprising: an unit that generates a random number γ of the b bits; a storage unit to store each of the indices y and the pre-calculated table C′ including each piece of element data C′[y] associated with each of the indices y; an unit that sets first to 2 b/2 -th pieces of the element data C′[y] of the pre-calculated table C′ in the storage unit to values C′[y]= 2 b/2 (0 ≦y< 2 b/2 −r H −1) C′[y]= 2×2 b/2 ( y= 2 b/2 −r H −1) C′[y]= 3×2 b/2 (2 b/2 −r H ≦y< 2 b/2 ) based on the index y and a number r H of upper b/2 bits of the number r; the unit that sets (2 b/2 +1)-th to (2×2 b/2 )-th pieces of the element data C′[y] of the pre-calculated table C′ in the storage unit to the value C′[y ]=γ(2 b/2 ≦y< 2×2 b/2 ) based on the index y and the random number γ; the unit that sets (2×2 b/2 +1)-th to (3×2 b/2 )-th pieces of the element data C′[y] of the pre-calculated table C′ in the storage unit to the values C′[y ]=γ(2×2 b/2 ≦y< 3×2 b/2 −r L ) C′[y]=γ+ 1(3×2 b/2 −r L ≦y< 3×2 b/2 ) based on the index y, the random number γ, and the number r L of lower b/2 bits of the number r; the unit that sets (3×2 b/2 +1)-th to (4×2 b/2 )-th pieces of the element data C′[y] of the pre-calculated table C′ in the storage unit to the value C′[y]=γ+ 1(3×2 b/2 ≦y< 4×2 b/2 ) based on the index y and the random number γ; a first extraction unit that extracts the number A 1 and the number A 2 from the number A; a second extraction unit that extracts a number A H of upper b/2 bits and a number A L of lower b/2 bits of the number A 2 from the number A 2 ; a first reading unit that sets the values of the (4×2 b/2 ) pieces of the element data C′[y] and then reads first element data C′[A H ] from the pre-calculated table C′ in the storage unit by using the extracted number A H as the index y; a second reading unit that reads second element data C′[C′[A H ]+A L ] from the pre-calculated table C′ in the storage unit by using a sum of the first element data C′[A H ] and the extracted number A L as the index y; and a carrying-over propagation unit that propagates carrying-over to the number A 1 by calculating A 1 +C′[C′[A H ]+A L ]−γ mod 2 (k−1)b based on the second element data C′[C′[A H ]+A L ], the random number γ, the number A 1 , and a number of bits (k−1)b of the number A 1 .