# DistinctDegreeFactorize(F, FP)ΒΆ

Package for the factorization of a univariate polynomial with coefficients in a finite field. The algorithm used is the “distinct degree” algorithm of Cantor-Zassenhaus, modified to use trace instead of the norm and a table for computing Frobenius as suggested by Naudin and Quitte .

distdfact: (FP, Boolean) -> Record(cont: F, factors: List Record(irr: FP, pow: Integer))
distdfact(p, sqfrflag) produces the complete factorization of the polynomial p returning an internal data structure. If argument sqfrflag is true, the polynomial is assumed square free.
exptMod: (FP, NonNegativeInteger, FP) -> FP
exptMod(u, k, v) raises the polynomial u to the kth power modulo the polynomial v.
factor: FP -> Factored FP
factor(p) produces the complete factorization of the polynomial p.
factorSquareFree: FP -> Factored FP
factorSquareFree(p) produces the complete factorization of the square free polynomial p.
irreducible?: FP -> Boolean
irreducible?(p) tests whether the polynomial p is irreducible.
separateDegrees: FP -> List Record(deg: NonNegativeInteger, prod: FP)
separateDegrees(p) splits the square free polynomial p into factors each of which is a product of irreducibles of the same degree.
separateFactors: List Record(deg: NonNegativeInteger, prod: FP) -> List FP
separateFactors(lfact) takes the list produced by separateDegrees and produces the complete list of factors.
trace2PowMod: (FP, NonNegativeInteger, FP) -> FP
trace2PowMod(u, k, v) produces the sum of u^(2^i) for i running from 1 to k all computed modulo the polynomial v.
tracePowMod: (FP, NonNegativeInteger, FP) -> FP
tracePowMod(u, k, v) produces the sum of u^(q^i) for i running and q= size F