REMAINDER ARITHMETIC UNIT USING DEFINING POLYNOMIAL IN FINITE FIELD

摘要

PROBLEM TO BE SOLVED: To execute a remainder calculation by a polynomial of a wider range by expandedly combining an efficient remainder calculation by means of a nondense polynomial such as a trinomial, a pentanomial, etc., and a method with respect to AOP. ;SOLUTION: A defining polynomial is selected by a selection means 1. For this purpose, when the degree of the defining polynomial is given, such a combination of (G, g) is sought (1) as satisfying G=gh concerning a nondense polynomial G (a polynomial in which the number of terms with coefficient of 1 is few) of a degree higher than (m) by at least 1. Using the combination (G, g), an arithmetic means 2 performs remainder calculation. A remainder (r) of a polynominal (f) by (g) can be obtained by r=(f mod G) mod g (2), when g is a factor of a nondense polynominal. In the formula, R=f mod G is efficiently obtainable by utilizing the fact that the polynomial G is of, and also, if (h) in G=gh has a low degree, the remainder (r) can easily be calculated.;COPYRIGHT: (C)2000,JPO