General  Information
Home
Important Dates
Conference Poster
Organizing Committee
Sponsors
 Program
Program and Schedule
Invited Talks
Contributed Talks
Tutorials
Posters
Software Exhibitions
 Registration
Information
Registered Participants
 Call  For
Research Papers
Posters
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Lodging
Traveling
Gastronomic Guide
Additional Information
 Miscellaneous
Social Events
Previous ISSACs
Other Events

 

 

Absolute polynomial factorization in two variables and the knapsack problem

G. Chèze

 

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. Then absolute factorization is reduced to finding the minimal zero sum relations between a set of approximated numbers b_i, i=1 to n. Here this problem with an a priori exponential complexity, is efficiently solved for large degrees (n>100). We rely on L.L.L. algorithm. For that purpose we prove a theorem on bounded integer relations between the numbers b_i, also called linear traces.

  issac2004 @ risc.uni-linz.ac.at