CoCoA » CoCoALib

The squarefree decomposition is the normal first step, but there are other problematic steps (e.g. mapping down to univariate by substitution).

Here is an example: ((x^3-x)*y+1)*((y^3-y)*x+1) in FF_3 any substitution will make one of the factors collapse to 1; to avoid this one normally passes to an algebraic extension, factorizes there, and then recombines the factors to obtain the factorization in the smaller field.
[actually, my information may be outdated now]

Kaltofen mapped down to bivariate; I think he showed that this is "safe with high probability". The final step down to univariate remains a problem though, I think. I will have to reread the relevant articles.

John Abbott wrote:

The squarefree decomposition is the normal first step, but there are other problematic steps (e.g. mapping down to univariate by substitution).

Here is an example: ((x^3-x)*y+1)*((y^3-y)*x+1) in FF_3 any substitution will make one of the factors collapse to 1; to avoid this one normally passes to an algebraic extension, factorizes there, and then recombines the factors to obtain the factorization in the smaller field.

ah, ok. Far more difficult that I thought.

Problem 2: and how difficult is it to factorize on an algebraic extension? (supposing we have algebraic extensions ;-)

Factorizing in F_q[x] is largely the same as factorizing in F_p[x]; the algorithm is essentially the same (but coeff arithmetic is not, of course).

Werner asked for a decent impl of F_q, at least for small field sizes. I just have to find the time and energy to do it...