Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime number.

For example I want to decompose $4x^6 + 20x^5 + 29x^4 - 14x^3 - 71x^2 - 48x$ as $(2x^4 + 7x^3 + 4x^2 - 13x - 16)(2x + 3)x$.

What algorithms do we have for such task?

P.S. Fast means lower arithmetic complexity. It would be good if algorithm is simple to use.

P.P.S. I want to implement requested algorithm by myself without using any computer algebra system like Maple, Magma and etc. I will start with $\mathbb F_p$ case.

• Sage uses FLINT flintlib.org to do factorisation in $\mathbb{Z}[X]$ and $\mathbb{Z}/n\mathbb{Z}[X]$. For an introduction into the very basic factorisation algorithms, maybe Cohen's "A course in computational number theory" pp. 124 could help. Apr 6 '15 at 21:24

2 Answers

The granddaddy of all methods for factoring polynomials over finite fields is the Berlekamp algorithm (see this Wikipedia article for a brief description). This should be simple enough that you can implement it without much trouble.

• It might be noted that while the Berlekamp algorithm is traditional, the Cantor–Zassenhaus algorithm is more efficient, and not more difficult to implement. Apr 7 '15 at 16:58

This is a large field, but it sounds like you have specific examples in mind, and not so much interested in theoretical results. If so, just use Mathematica or Maple or Magma or... (Maple has better polynomial factorization algorithms, but most of the time you won't notice) If you actually want to know what the algorithms do, read the oeuvre of Mark van Hoeij, who has the best algorithms currently known (I should note that modulo a prime factoring is very easy, it is $\mathbb{Z}$ which is hard).

• I want to implement requested algorithm by myself without using some computer algebra system like Maple, Magma and etc. I will start with $\mathbb F_p$ case. Is it true that Mark van Hoeij link is the best start for me? Apr 7 '15 at 15:32
• I assume that you want to do this as an exercise in programming; otherwise there are free open-source high quality implementations, such as FLINT (flintlib.org) Or is it something else? Apr 7 '15 at 15:53
• @DimaPasechnik, it is something else. I want to implement some algorithm that significantly depends on that factorization algorithm. And I have GPU as target platform, so it isn't easy to use external libraries. But thanks for link, may be I will steal realization from flint! Apr 7 '15 at 18:42
• GPU-using algorithms for factorisation is an active research area, see e.g. csd.uwo.ca/~moreno/Publications/Moreno-Maza.Pan.HPCS-2010.pdf. I'd guess that procedures using linear algebra routines a lot would be performing better, as for them there are well-optimised routines available. Apr 7 '15 at 20:43