ChapterZero

Kronecker’s Method of Factoring Polynomials over $\Q[x]$

Kronecker’s method is beautiful: it’s simple, and it always works. Here’s the idea:

Given a polynomial $f \neq 0 \in \Z[x]$ , we are trying to decide if is reducible (can be expressed as the product of two polynomials in $\Z[x]$ , neither of which is 1 or -1), and if so to determine its factors, or irreducible (any factorization of is trivial, in that it involves factoring out 1 or -1).

Note that if is of degree and we assume it is reducible to $f = g \cdot h$ , without loss we can assume that has degree less than or equal to $\lfloor \frac{n}{2} \rfloor$ — because if not, we would just switch with the associated .

Next, find $\{z_i\}_{i=1,\ldots,\lfloor \frac{n}{2} \rfloor} \subset \Z$ such that $\forall_i f(z_i) \neq 0$ . Then $g(z_i) \mid f(z_i)$ .

Construct all of degrees 0 (excluding -1 and 1) through $\lfloor \frac{n}{2} \rfloor$ such that g(z_i) is a divisor of f(z_i) for $i=1,\ldots, \deg(g)$ ; you can use Lagrange polynomial interpolation to do this. Then test (using synthetic divison, for example) all these candidate to find which divide .

Pretty neat! Just reading the algorithm makes you want to program it up— in Scheme, no less!

To extend this algorithm for use in factorizing polynomials in $\Q[x]$ is left as an exercise for the reader :).

Update
As I started to code this up, I realized synthetic division only applies when you are dividing by a linear factor— no biggie, just use polynomial long division. Here’s a simple algorithm to calculate $(Q,R)=\text{Div}(a,b)$ , where Q,R are such that $a = Q\cdot b + R$ :

if $\deg(b) > \deg(a)$ , then return
else,
- $p= \frac{a_{\deg(a)}}{b_{\deg(b)}}$
- $P=(p,\ldots,0)$ such that $\deg(P)=\deg(a)-\deg(b)$
- $a^\prime = a - b \cdot P$
- $(Q^\prime, R^\prime) = \text{Div}(a^\prime, b)$
- $(Q,R) = (Q^\prime+P, R^\prime)$

This entry was posted on Saturday, February 19th, 2005 at 6:35 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Kronecker’s Method of Factoring Polynomials over $\Q[x]$ ”

Steve Says:
February 20th, 2005 at 12:21 pm
In fact synthetic division can be done when dividing by a quadratic (and, although I haven’t tried it, I suspect also by higher degree polynomials).
Here’s a page from a Numerical Analysis book from yesteryear that shows the method.
Alex Says:
February 23rd, 2005 at 9:36 am
Thanks for the page; when I programmed in that poly divison algorithm I came up with, it doesn’t seem to work. Maybe it’s just my programming skills suck, but it is nice to have an example to emulate.

Kronecker’s Method of Factoring Polynomials over

2 Responses to “Kronecker’s Method of Factoring Polynomials over ”

Leave a Reply

Kronecker’s Method of Factoring Polynomials over $\Q[x]$

2 Responses to “Kronecker’s Method of Factoring Polynomials over $\Q[x]$ ”