Factoring multivariate polynomials over algebraic number fields. (English) Zbl 0636.12005
In this paper the author generalizes the method of himself, H. W. Lenstra jun. and L. Lovász [Math. Ann. 261, 515–534 (1982; Zbl 0488.12001)] to factoring of polynomials over algebraic number fields \(F\). The result is an algorithm which is polynomial-time in the degrees and the coefficient-size of the polynomial to be factored. The main ideas are to specialize the given polynomial – say in \(n\) variables \(x_1,\ldots,x_n\) – for \(x_2,\ldots, x_n\) suitably and then to exhibit a factor of the resulting polynomial in the variable \(x_1\) over \(F\) by approximating a \(p\)-adic factor and making use of lattice basis reduction analogously to the rational case. The author himself mentions that the obtained algorithm is more of theoretical than of practical interest. He gives detailed references to other methods.
Reviewer: Michael Pohst (Düsseldorf)
MSC:
11Y16 | Number-theoretic algorithms; complexity |
11Y40 | Algebraic number theory computations |
11R09 | Polynomials (irreducibility, etc.) |
68W30 | Symbolic computation and algebraic computation |