US 8,488,780 B2 · Finite field calculation apparatus, finite field calculation method and recording medium

Abstract

A calculation Πi=0N−1e(R(i, 0), . . . , R(i, K−1)) where a calculation of K elements R(i, k)εGF(pm) of a finite field GF(pm) over a finite field is expressed as e(R(i, 0), . . . , R(i, K−1)) is efficiently performed. Polynomials poly(R(i, 0), . . . , R(i, K−1)) that express a d-th-order extension field of the finite field GF(pm), which are obtained by the calculations e(R(i, 0), . . . , R(i, K−1)) for different values of i, are multiplied by each other, and a cumulative multiplication of the products is performed, for example. The polynomial poly(R(i, 0), . . . , R(i, K−1)) is a mapping from the input elements of the finite field GF(pm), and the coefficients of at least some of the terms thereof are 0. The same process is performed for different sets of values of i, and the calculation Πi=0N−1e(R(i, 0), . . . , R(i, K−1)) is performed using the result.

A finite field calculation apparatus, comprising:

an input part adapted to accept N*K elements R(i, k)εGF(pm) of a finite field GF(pm) where N≧2, K≧1, iε{0, . . . , N−1}, kε{0, . . . , K−1}, p represents a prime number, and m represents an integer equal to or greater than 1;
a finite field calculation part adapted to perform a calculation Πi=0N−1e(R(i, 0), . . . , R(i, K−1)) where e(R(i, 0), . . . , R(i, K−1)) represents a calculation of K elements R(i, 0), . . . , R(i, K−1)εGF(pm) of the finite field GF(pm) over a finite field;
and
an output part adapted to output a result of the calculation performed by the finite field calculation part,
wherein the calculation e(R(i, 0), . . . , R(i, K−1)) over the finite field includes an extension field calculation over a d-th-order extension field GF(pd·m) of the finite field GF(pm) where d≧2,
the extension field calculation is a calculation that maps images over the finite field GF(pm) that depend on one or more input elements R(i, k)ε{R(i, 0), . . . , R(i, K−1)} of the finite field GF(pm) and/or the elements R(i, k)ε{R(i, 0), . . . , R(i, K−1)} of the finite field GF(pm) to a polynomial poly(R(i, 0), . . . , R(i, K−1))εGF(pd·m) that expresses an element of the d-th-order extension field GF(pd·m),
the polynomial poly(R(i, 0), . . . , R(i, K−1))εGF(pd·m) is a polynomial having d terms, coefficients of the d terms include coefficients ah of some terms hε{0, . . . , d−1} and coefficients ar of predetermined some terms rε{0, . . . , d−1} (r≠h), the coefficients ah are the images over the finite field GF(pm) that depend on one or more input elements R(i, k) of the finite field GF(pm) and/or the elements R(i, k) of the finite field GF(pm), and the coefficients ar are previously determined to be 0εGF(pm), and
the finite field calculation part includes:
a first calculation part adapted to receive, for any i1ε{0, . . . , N−1}, images over the finite field GF(pm) that depend on one or more elements R(i1, k) of the finite field GF(pm) and/or the elements R(i1, k) of the finite field GF(pm) and to perform the extension field calculation therefor to obtain a polynomial poly(R(i1, 0), . . . , R(i1, K−1))εGF(pd·m);
a second calculation part adapted to receive, for any i2ε{0, . . . , N−1} (i2≠i1), images over the finite field GF(pm) that depend on one or more elements R(i2, k) of the finite field GF(pm) and/or the elements R(i2, k) of the finite field GF(pm) and to perform the extension field calculation therefor to obtain a polynomial poly(R(i2, 0), . . . , R(i2, K−1))εGF(pd·m);
a third calculation part adapted to receive the polynomial poly(R(i1, 0), . . . , R(i1, K−1)) and the polynomial poly(R(i2, 0), . . . , R(i2, K−1)) and calculate product thereof as poly(R(i1, 0), . . . , R(i1, K−1))·poly(R(i2, 0), . . . , R(i2, K−1))εGF(pd·m);
a control part adapted to select each element of a subset including L different elements of the set {0, . . . , N−1} one time as i1 or i2, where L represents an even number, and run first processing stages, each of which includes processing stages performed by the first calculation part, the second calculation part and the third calculation part, each of the first processing stages are performed one time for each pair of selected i1 and i2, to perform a loop process including the first processing stages for L/2 pairs of selected i1 and i2;
and
a fourth calculation part adapted to calculate Πi=0N−1poly(R(i, 0), . . . , R(i, K−1))εGF(pd·m) using products poly(R(i1, 0), . . . , R(i1, K−1))·poly(R(i2, 0), . . . , R(i2, K−1)) obtained by the first processing stages.

11 more elements

Finite field calculation apparatus, finite field calculation method and recording medium

Life of this patent

Finite field calculation apparatus, finite field calculation method and recording medium

Life of this patent

Abstract

Claims45