Factorization

[Bernard Parisse]

"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?