Studies on factoring polynomials over global fields

Benzaoui, Ilhem (2007-12)

Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2007.


In this thesis, we surveyed the most important methods for factorization of polynomials over a global field, focusing on their strengths and showing their most striking disadvantages. The algorithms we have selected are all modular algorithms. They rely on the Hensel factorization technique, which can be applied to all global fields giving an output in a local field that can be computed to a large enough precision. 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 techniques have 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 running time. This appears for instance in the latest method due to van Hoeij, concerning the factorization over a number 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 as part of the properties of these algorithms.

Please refer to this item in SUNScholar by using the following persistent URL:
This item appears in the following collections: