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.
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
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. the NTL web site. Regards, Wolfgang