Factorization

[Wolfgang Abele]

Am Sonntag,  8. Juli 2001 13:56 schrieben Sie:
> Factoring over algebraic extension is indeed not difficult. 
> In short, if P(X,Y) is a polynomial of X where Y denotes
> the algebraic extension, and Q(Y) the minimal polynomial of Y,
> you compute the resultant N(X) with respect to Y of P(X+kY,Y) and Q(Y),
> where k is an integer such that the resultant N is square-free. Then
> the factors of P(X,Y) are the gcd of the factors of N(X+kY) and Q(Y).
This is the standard Trager algorithm. Like you're saying, you need to have a 
gcd over extensions and resultant as subroutines. If Richy provides that 
adaptor stuff, I'll try and implement Trager. If anybody's interested in the 
more difficult multivariate factorization I could provide him or her with a 
step-by-step guide to start with.

Incidentally, the problem with Trager is that it soon becomes inefficient 
with high degree polynomials. This is because the polynomial's coefficients 
and degree become much bigger in the norm polynomial. Also, the norm tends to 
have many modular factors. People are currently looking into whether Trager 
can be improved by the new knapsack algorithm, either through faster 
factorization of the norm or a direct application to the algebraic extensions.

> BTW, I have not checked NTL recently, but last year, it did not
> implement the best reconstruction algorithm which is AFAIK the knapsack
> algorithm (based on LLL). Did that change?
There is an implementation for NTL written by Paul Zimmermann. It's linked on 
the NTL web site.

Regards, Wolfgang