Patent ID: 8543630

Claim:
A computing device for cryptographic processing that calculates a square of an element in a finite field, the finite field being a 2r-th degree extension field Fq^{2r} (^ denotes an exponent, and r denotes a prime number), the computing device comprising: an accept unit that accept a plurality of elements in the finite field, the elements being the vector representation; a multiplying unit configured to perform multiplication operations on a base field Fq using the accepted elements and obtain a multiplication value, one of the multiplication operations being determined by a first condition, and the other one of the multiplication operations being determined by a second condition, the first and second conditions being conditions under which the element in the finite field to be placed in an algebraic torus, the first condition using a characteristic in which the element of the 2r-th degree extension field is an element of an algebraic torus T2r(Fq), and the second condition using a characteristic in which the element of the 2r-th degree extension field is an element of the algebraic torus T2(Fq^r); an adding and subtracting unit configured to perform an addition and subtraction operation using the obtained multiplication value and the accepted elements, and obtain a calculation result of the square of the element, the addition and subtraction operation being determined by the first and second conditions; and an output unit configured to output the obtained calculation result, wherein the first condition is a condition in which the element of the 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2r(q) (.PHI.n(x) is a n-th cyclotomic polynomial) and the second condition is a condition in which an element of a 2r-th degree extension field is ‘1’ when raised to a power of .PHI.2(q^r) (q denoting a characteristic of an extension field).