ROOT CALCULATING METHOD AND ROOT CALCULATING CIRCUIT FOR QUADRATIC POLYNOMIAL ON FINITE BODY

摘要

PROBLEM TO BE SOLVED: To provide a root calculating circuit for a quadratic polynomial on a finite body which is fast and reducible in actual circuit scale and uses a polynomial base. ;SOLUTION: This circuit consists of (m-3) cascaded exclusive OR elements X(1, 0) to X(1, m-4) which input at one-input sides corresponding bits of an arbitrary element a=(a₀, a₁...a_n-1) on a finite body GF(2^m) and at the other-input side the outputs of precedent elements or a_m-1 for X(1,0) instead of the output of the precedent element and (m/2-1) exclusive OR elements X(2, 0) to X(2, m/2-2) which input at one-input sides the outputs of a_m-1 and the outputs of X(1, 1), X(1, 3)...X(1, m-5) and a₀ at the other-input sides. The outputs of the elements X(2,0) to X(2, m/2-2) and the outputs of the elements X(1, 0), X(1, 2) to X(1, m-4) are outputted as the root z=(z₀, Z₁...Z_m-1 of said a₀.;COPYRIGHT: (C)1999,JPO