Absolute Polynomial Factorization in Two Variables and the Knapsack Problem

摘要

A recent algorithmic procedure for computing the absolute factorization of a polynomial P(X, Y), after a linear change of coordinates, is via a factorization modulo X~3. This was proposed by A. Galligo and D. Rupprecht in [7], [16]. Then absolute factorization is reduced to finding the minimal zero sum relations between a set of approximated numbers b_i, i = 1 to n such that ∑ from i=1 to n of b_i =0, (see also [17]). Here this problem with an a priori exponential complexity, is efficiently solved for large degrees (n > 100). We rely on LLL algorithm, used with a strategy of computation inspired by van Hoeij's treatment in [23]. For that purpose we prove a theorem on bounded integer relations between the numbers bi, also called linear traces in [19].