abele at kingmemo.de
Mon Jul 9 09:05:00 CEST 2001
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.
More information about the GiNaC-devel