1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Wuthrich
    Commented Apr 6, 2015 at 21:24

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ It might be noted that while the Berlekamp algorithm is traditional, the Cantor–Zassenhaus algorithm is more efficient, and not more difficult to implement. $\endgroup$
    – Emil Jeřábek
    Commented Apr 7, 2015 at 16:58
2
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Maxim
    Commented Apr 7, 2015 at 15:32
  • 1
    $\begingroup$ 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? $\endgroup$
    – Dima Pasechnik
    Commented Apr 7, 2015 at 15:53
  • $\begingroup$ @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! $\endgroup$
    – Maxim
    Commented Apr 7, 2015 at 18:42
  • 3
    $\begingroup$ 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. $\endgroup$
    – Dima Pasechnik
    Commented Apr 7, 2015 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .