13.3. Rabin's irreducibility test🔗

Rabin's criterion avoids constructing a complete factorization. A monic polynomial f of degree n over 𝔽_p is irreducible exactly when f ∣ X^(p^n) - X and, for every prime divisor q of n, gcd(f, X^(p^(n/q)) - X) = 1.

The first condition says that all roots of f lie in 𝔽_(p^n). The remaining conditions rule out roots in every proper maximal subfield. Hex checks the criterion by modular exponentiation and greatest-common-divisor computations and records the intermediate data in an irreducibility certificate.