Patent ID: 6484192
Filing Date: 2002-11-19
Classification: H03M

Abstract:
A root finding circuit of a quadratic polynomial over a finite field, for finding roots of a quadratic polynomial z2+z+a over a finite field GF(2m) with respect to an arbitrary element a=(a0, a1, . . . , amâˆ’1) over the finite field GF(2m), a polynomial f=xm+xmâˆ’1+. . . x+1 over GF(2) being irreducible and having an expansion degree m, said f being used as a generation polynomial of GF(2m), said root finding circuit comprising:mâˆ’3 cascade-connected exclusive OR gates X(1, 0) to X(1, mâˆ’4) each supplied with a corresponding bit of said element â€œaâ€  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, wherein outputs of said exclusive OR gates X(2, 0) to X(2, m/2âˆ’2), outputs of said exclusive OR gates X(1, 0), X(1, 2), . . . , X(1, mâˆ’4), and said a0 are output as a root z=(z0, z1, . . . , zmâˆ’1) of z2+z+a.