ToySolver.Data.Polynomial.Factorization.FiniteField

Factoriation of polynomial over a finite field.

References:

• http://en.wikipedia.org/wiki/Factorization_of_polynomials_over_a_finite_field_and_irreducibility_tests
• http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm
• Martin Kreuzer and Lorenzo Robbiano. Computational Commutative Algebra 1. Springer Verlag, 2000.

Documentation

factor :: forall k. (Ord k, FiniteField k) => UPolynomial k -> [(UPolynomial k, Integer)]

sqfree :: forall k. (Eq k, FiniteField k) => UPolynomial k -> [(UPolynomial k, Integer)]

Square-free decomposition of univariate polynomials over a finite field.

berlekamp :: forall k. (Eq k, Ord k, FiniteField k) => UPolynomial k -> [UPolynomial k]

Berlekamp algorithm for polynomial factorization.

Input polynomial is assumed to be monic and square-free.

basisOfBerlekampSubalgebra :: forall k. (Ord k, FiniteField k) => UPolynomial k -> [UPolynomial k]

Orphan instances

KnownNat p => SQFree (UPolynomial (PrimeField p))

Methods

sqfree :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)]

KnownNat p => Factor (UPolynomial (PrimeField p))

Methods

factor :: UPolynomial (PrimeField p) -> [(UPolynomial (PrimeField p), Integer)]