# 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

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