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.