DistinctDegreeFactorize(F, FP)

ddfact.spad line 1 [edit on github]

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: NonNegativeInteger))

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