Studies on factoring polynomials over global fields

[摘要] In this thesis, we surveyed the most important methods for factorization of polynomials over a globalfield, focusing on their strengths and showing their most striking disadvantages. The algorithms wehave selected are all modular algorithms. They rely on the Hensel factorization technique, which canbe applied to all global fields giving an output in a local field that can be computed to a large enoughprecision. The crucial phase of the reconstruction of the irreducible global factors from the local ones,determines the difference between these algorithms. For different fields and cases, different techniqueshave been used such as residue class computations, ideal calculus, lattice techniques.The tendency to combine ideas from different methods has been of interest as it improves the runningtime. This appears for instance in the latest method due to van Hoeij, concerning the factorization over anumber field. The ideas here can be used over a global function field in the form given by Belabas et al.using the logarithmic derivative instead of Newton sums.Complexity analysis was not our objective, nevertheless it was important to mention certain results aspart of the properties of these algorithms.

[发布机构] Stellenbosch University