# 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`k`

th 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`