Where To Go

implementation of factorization over F_q: Cantor-Zassenhaus, Berlekamp

• improvements of Cantor-Zassenhaus:
• use minimal polynomials for the equal degree factorization stage (see V. Shoup, A new polynomial factorization algorithm and its implementation) -> requires Berlekamp/Massey algo -> Pade approximation

• special type for polys over F_2 and extensions thereof

• F_q for non-word size p

algebraic number fields:

• straight forward implementation: use a precomputed inverse of the minpoly and reduce multiplication in Q(\alpha) to multiplication in Q[x] and reduce everything using the precomputed inverse but maybe there are smarter ways ?
• polynomials over algebraic number fields: multiplication->reduce to multiplication in Q[x] by Kronecker substitution

gcd of polynomials over algebraic number fields:

• gcd over (Z_{p}[t]/(f))[x] for not necessarily irreducible f
• fast rational reconstruction
• fast divisibility testing

factorization of polynomials over algebraic number fields:

Trager's norm based algorithm needs:

• modular resultant computation
• fast factorization over Z[x]

knapsack LLL factorization a la Belabas:

• needs LLL ;-)
• factorization over (Z_{p}[t]/(f)) for an irreducible f
• Hensel lifting from (Z_{p}[t]/(f))[x] to (Z_{p^{k}}[t]/(f))[x] for an irreducible f
• naive factor recombination for easy cases
• LLL based reconstruction.

---

Maybe it's worth to take a look at Belabas' original paper and at a paper by Belabas, van Hoeij, Klüners, Steel and use the latter plus ideas from Novocin to get a better algorithm.

---