Finite Field Computation

Root Finding over Finite Fields

Finding roots of a polynomial in a finite field by GCD with the Frobenius polynomial followed by probabilistic splitting.

Engineering / MathematicsFinite Field Computation2 min readKV-MATH-0526

Finding the roots of a polynomial in a finite field is a two-stage problem: isolate the part of the polynomial that splits into linear factors, then separate those factors. The first stage is deterministic; the second is probabilistic.

Stage one: isolate the linear part

Every element of the field satisfies the Frobenius identity, so the polynomial X^q - X is exactly the product of all linear factors over the field. Taking a GCD with it discards everything else.

g(X) = gcd( f(X), X^q - X )g is the product of the distinct linear factors of f.

Isolating the linear factors

Compute the Frobenius powerCompute X^q modulo f by repeated squaring on polynomials — never expand X^q itself.
Subtract XForm the residue of X^q - X modulo f.
Take the GCDThe GCD with f is the product of distinct roots.
Check for noneIf the GCD is constant, f has no roots in the field.

Stage two: split the linear part

The product of linear factors must now be separated. For odd characteristic the standard method exploits the fact that half the non-zero elements are squares.

gcd( g(X), (X + a)^((q-1)/2) - 1 ) for random aSplits g by whether each root plus a is a square.

Special cases worth handling directly

Small degrees are worth special-casing
Degree of f	Method
1	Read the root off directly
2	Complete the square and apply Shanks-Tonelli
3, 4	Closed-form resolvents exist but the general method is usually simpler
Large	The two-stage method above

Characteristic two

Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.6.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.