| Factoring polynomials is a central problem in computational algebra and number theory and is a basic routine in most computer algebra systems (e.g. Maple, Mathematica, Magma, etc). It has been extensively studied in the last few decades by many mathematicians and computer scientists. The main approaches include Berlekamp's method (1967) based on the kernel of Frobenius map, Niederreiter's method (1993) via an ordinary differential equation, Zassenhaus's modular approach (1969), Lenstra, Lenstra and Lovasz's lattice reduction (1982), and Gao's method via a partial differential equation (2003). These methods and their recent improvements due to van Hoeij (2002) and Lecerf et al (2006-- 2007) provide efficient algorithms that are widely used in practice today.;This thesis studies two issues on polynomial factorization. One is to improve the efficiency of modular approach for factoring bivariate polynomials over finite fields. The usual modular approach first solves a modular linear equation (from Berlekamp's equation or Niederreiter's differential equation), then performs Hensel lifting of modular factors, and finally finds right combinations. An alternative method is presented in this thesis that performs Hensel lifting at the linear algebra stage instead of lifting modular factors. In this way, there is no need to find the right combinations of modular factors, and it finds instead the right linear space from which the irreducible factors can be computed via gcd. The main advantage of this method is that extra solutions can be eliminated at the early stage of computation, so improving on previous Hensel lifting methods.;Another issue is about whether random numbers are essential in designing efficient algorithms for factoring polynomials. Although polynomials can be quickly factored by randomized polynomial time algorithms in practice, it is still an open problem whether there exists any deterministic polynomial time algorithm, even if generalized Riemann hypothesis (GRH) is assumed. The deterministic complexity of factoring polynomials is studied here from a different point of view that is more geometric and combinatorial in nature. Tools used include Grobner basis structure theory and graphs, with connections to combinatorial designs. It is shown how to compute deterministically new Grobner bases from given Gobner bases when new polynomials are added, with running time polynomial in the degree of the original ideals. Also, a new upper bound is given on the number of ring extensions needed for finding proper factors, improving on previous results of Evdokimov (1994) and Ivanyos, Karpinski and Saxena (2008). |
