#### Date of Award

8-2009

#### Document Type

Dissertation

#### Degree Name

Doctor of Philosophy (PhD)

#### Legacy Department

Mathematics

#### Committee Chair/Advisor

Gao, Shuhong

#### Committee Member

Maharaj , Hiren

#### Committee Member

Matthews , Gretchel L

#### Committee Member

Dimitriova , Elena S

#### Abstract

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 Gr'{o}bner basis structure theory and graphs, with connections to combinatorial designs. It is shown how to compute deterministically new Gr'{o}bner bases from given G'{o}bner 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).

#### Recommended Citation

Guan, Genhua (yinhua), "Factoring Polynomials and Groebner Bases" (2009). *All Dissertations*. 503.

https://tigerprints.clemson.edu/all_dissertations/503