Patent ID: 8438205
Filing Date: 2013-05-07
Classification: G06F

Abstract:
1. A computing device that calculates a square of an element in a finite field, the finite field being a 2r-th degree extension field Fq^{2r}, where ^ denotes an exponent, and r denotes a prime number, the computing device comprising: an accept unit configured to accept a plurality of elements in the finite field, the elements having a vector representation; a creating unit configured to create first and second conditions under which the element in the finite field is 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 the 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); a multiplying unit configured to perform multiplication operations on a base field Fq using accepted elements and to obtain a multiplication value, one of the multiplication operations being determined by the first condition, and another one of the multiplication operations being determined by the second condition; an adding and subtracting unit configured to perform an addition and subtraction operation using the multiplication value and the accepted elements, and to 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 calculation result, wherein the creating unit is configured to create the first condition such that the element of the 2r-th degree extension field is ‘1’ when raised to a power of Φ2r(q), where Φn(x) is a n-th cyclotomic polynomial, and to create the second condition such that an element of the 2r-th degree extension field is ‘1’ when raised to a power of Φ2(q^r), where q denotes a characteristic of an extension field.