"Richard B. Kreckel" wrote:
Also, NTL doesn't support multivariate polynomials, calculations in Q, and algebraic extensions of Q.
Q is a no-brainer once the lifting is in place. It is the latter which we know nothing about over here. Are algebraic extensions really difficult? I remember Bernard Parisse once claimed they are not. Bernard?
Factoring over algebraic extension is indeed not difficult. The algorithm can be found for example in the excellent book of number theory of Henri Cohen (See algorithm 3.6.4 in Henri Cohen book). 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). The implementation in giac is in the gausspol.cc file (functions ext_factor and algfactor). 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?