ROOT FINDING METHOD AND ROOT FINDING CIRCUIT OF QUADRATIC POLYNOMIAL OVER FINITE FIELD

There is provided a root finding circuit of a quadratic polynomial over a finite field, capable of operating at high speed and making the circuit scale in implementation small.The root finding circuit includes m−3 cascade-connected exclusive OR gates X(1, 0) to X(1, m−4) each supplied with a corresponding bit of an arbitrary element “a=(a0, a1, . . . , am−1)” over a finite field GF(2m) at a first input thereof and each supplied with output of an exclusive OR gate of an immediately preceding stage at a second input, a second input of only X(1, 0) being supplied with am−1 instead of the output of an exclusive OR gate of an immediately preceding stage, and m/2−1 exclusive OR gates X(2, 0) to x(2, m/2−2) respectively supplied with am−1 and outputs of X(1, 1), X(1, 3), . . . , X(1, m−5) at first inputs and each supplied with a0 at a second input thereof. Outputs of the exclusive OR gates X(2, 0) to X(2, m/2−2), outputs of the exclusive OR gates X(1, 0), X(1, 2), . . . , X(1, m−4), and the a0 are output as a root z=(z0, z1, . . ., zm−1) of z2+z+a.