13.1. The problem🔗

HexBerlekamp factors dense polynomials over the prime field 𝔽_p. Its principal executable type is Hex.FpPoly. The library also supplies Rabin's irreducibility test and a distinct-degree factorization.

For a monic square-free polynomial f of degree n, Berlekamp's method studies the Frobenius map h ↦ h^p mod f on the n-dimensional vector space 𝔽_p[X] / (f). In the basis 1, X, ..., X^(n-1), subtracting the identity gives the Berlekamp matrix Q_f - I.