The problem of factoring multivariate polynomials can be distinguished as rational factorization and absolute factorization.
The first is over the ground field while the latter over the algebraic closure. Both cases are fundamental in number theory,
algebraic geometry, and  computer algebra systems.  We have contributed in the following areas:

        Factoring univariate polynomials
     Factoring multivariate polynomials via PDE
     Polytopes and polynomials
     Hensel lifting and factoring
 

Factoring univariate polynomials

In \cite{GS98}, we show how to efficiently compute roots of polynomials over a function field of a plane curve. This improves the recent list-decoding algorithm of Sudan (1996) for algebraic codes (including Reed-Solomon codes) beyond the usual correction capability.

In \cite{Gao96a}, we design an algorithm for factoring polynomials over large prime fields $\fp$. Under ERH, the algorithm can split in deterministic polynomial time all polynomials except those that satisfy some  stringent condition called {\em super square balanced}.  It is conjectured that  super square balanced polynomials do not exist.

In \cite{BGM93,BGM94},  we give  complete explicit factorizations of polynomials of special forms.

In \cite{GG94}, we discuss Niederreiter's algorithm (1993) for factoring polynomials over small finite fields and  compare it to Berlekamp's (1967).  We present a probabilistic factorization algorithm via a fast solver for systems of linear equations.  This approach is particularly interesting in characteristic two, where it seems faster than Kaltofen's adaptation of Berlekamp's factorization algorithm.
 

Factoring polynomials via PDE

In \cite{Gao00}, we present a new method based on  partial differential equations for both rational factorization and absolute factorization.  This method is in some sense a parallel theory for bivariate polynomials to those of Berlekamp and Niederreiter for univariate polynomials. Such a method  had been sought after ever since Niederreiter discovered his method using ordinary differential equations.

For both rational factorization and  absolute factorization, our method  has a near quadratic time complexity, greatly improving previous algorithms, for examples, Chistov (1984, 1987, 1991), Duval (1991), Grigoryev (1984), Grigoryev and Chistov (1984), A. Lenstra (1984, 1985, 1987), Kaltofen (1985, 1995), von zur Gathen and  Kaltofen (1985),  among others.  Computer experiments indicate that our method is not only simple but practical.

Also, a new effective Hilbert  irreducibility theorem is proved in \cite{Gao00} which allows an efficient reduction of polynomials from multivariate to bivariate.

Decomposation of polytopes and polynomials

The concept of Newton polytope for multivariate polynomials goes back to  A. M. Ostrowski (1921,1976).  He observed that if a polynomial factor then its Newton polytope decomposes in the sense of Minkowski sum of the Newton polytopes of its factors and he commented that this can be useful for factoring polynomials. In \cite{Gao98}, we  introduce the concept of integral indecomposability of polytopes and obtain a simple but extremely useful irreducibility criterion.

We give two general constructions of indecomposable polytopes which allows explicit constructions of many infinite families of absolutely irreducible polynomials.  These polynomials have the nice properties of remaining irreducible when their coefficients vary arbitrarily in the ground field, provided some specific of them being nonzero. This is useful in number theory and algebraic geometry (say for a moving family of varieties or when some kind of deformation is desired).  These constructions also  includes the well-known criteria of  Eisenstein (1850), Dumas (1906) and Stepanov-Schmidt (1976) as special cases.

In \cite{GL99}, we discuss the computational complexity of decomposing polytopes and its implications in factoring polynomials.  We prove that the problem of deciding decomposability of integral polytopes in $\R^n$ is $NP$-complete.  The result remains true even in dimension 2 (i.e.\ $n=2$).  Here the input size is the binary representations of the coordinates of the vertices of the polytopes. This corresponds to sparse representation of polynomials.

We give a deterministic algorithm for decomposing polygons, with running time is almost linear in the areas of the polygons.  For higher dimensions, we use a projection lemma of ours to design an efficient probabilitic algorithm for testing indecomposability of Newton polytopes, so an algorihtm for testing absolute irreducibility of multivariate polynomials.  This method does not work for some polynomials, but very fast for most polynomials, much faster than any infallible algoritm mentioned above, say the PDE method.  The computer experiments in \cite{GL00b} indicate that our method is efficient for polynomials with $O(nd)$ terms where $n$ is the number of variables and $d$ is the degree in each variable.  For example, for a random polynomial with $n=10$, $d=20$ and 500 terms, our algorithm takes less than a second on a 550 MHz PC with 128 MB RAM; for a random polynomial with $n=100$, $d=10$ and  $200$ terms, it takes about two seconds.

Hensel lifting and factoring

It is well known that the Hensel lifting technique provides practical methods for factoring polynomials over various fields. Such methods are known to run in exponential time in the worst case, but seem fast for most polynomials. The latter phenomenon has not been fully understood and calls for an average running time analysis. The only analysis we know of is that of Collins (1979) for univariate integral polynomials (factoring over the rational numbers). He shows,  under some reasonable number theoretic conjectures, that the average running time is indeed polynomial.  In [GaL00a], we present a rigorous analysis for bivariate polynomials over finite fields.  We show that  the average running time is almost linear in the input size.  More precisely, for all bivariate polynomials of total degree $n$ over a fixed finite field, the average running time is $\Oh(N)$ using fast polynomial arithmetic, and $\Oh (N^{1.5})$ using standard polynomial arithmetic where $N=n^2$ represents the input size and we ignore the logarithmic factors in our running times.  This explains for the first time  why the Hensel lifting technique is fast in practice for bivariate polynomials over finite fields.

Normal bases offer considerable advantages in efficient finite field arithmetic.  Optimal normal bases in finite fields were introduced at the University of Waterloo by Mullin et al.\ (1989), and are  used in practical hardware implementation of public-key cryptosystems.  In the same paper, Mullin et al.\  construct two families of optimal normal bases and, based on a computer experiment, conjecture that there are no new ones. This conjecture had remained open for several years before H.W. Lenstra, Jr. (1991) proved it for finite fields over $\ftwo$. Lenstra's method, however,  is not applicable to other fields.  In \cite{Gao92}, we confirmed the conjecture for all finite fields by using a substantially different argument.  It turns out that the conjecture holds for any finite Galois extension of an arbitrary field and the proof for the general case is again different but simpler. The final result is published in [Gal92a].

By our classification in \cite{GL92}, not all  finite fields have optimal normal bases.  In the latter case, it is desirable to have a normal basis of low complexity.  In \cite{BGM94}, we construct several families of such bases, which come from the factorization of $cx^{q+1}+d x^q -ax -b$ over $\fq$.  In \cite{Gao97b}, we show that general Gauss periods can be used to construct many new normal basis of low complexity.  A by-product of the work in \cite{Gao97b} is a discovery of an interesting structure theorem of finite abelian groups.

An element of a finite field is called completely normal if it is normal over every intermediate subfield.  The existence of  completely normal elements is proved by Blessenohl and Johnsen (1986), but their proof is not constructive.  In \cite{BGM97}, we construct several infinite families of explicit irreducible polynomials whose roots are completely normal.

In \cite{GP97b}, we study the density of normal elements in finite fields and improve previous known lower bounds.  We also give an upper bound that is almost tight with the lower bounds.  These results are useful in analyzing Wiedemann's algorithm (1986) for solving large systems of sparse linear equations over finite fields.

In \cite{GGP96a}, we prove that for a small prime $p$ and infinitely many integers $n$, exponentiation of an arbitrary element in $\fpn$ can be done with $O(n^2 \log\!\log n)$ operations in $\fp$.  The previous best time was  $O(n^2 \log n \log\!\log n)$.  An implementation for fields $\ftwon$, $n\leq 10000$, shows that our algorithm indeed performs much superior to others.

In cryptographical applications, it is important to have elements in finite fields that are primitive (or have high multiplicative orders) and large powers of them can be computed quickly.  In \cite{GV95,GGP98}, we show that Gauss periods over finite fields have exactly these desired properties.  More precisely, we discover by experimental results that  Gauss periods always have high multiplicative orders and are frequently primitive in finite fields. This implies that Gauss periods in finite fields generate a great many primitive normal bases and primitive self-dual normal bases as well. We also prove that Gauss periods can be exponentiated in quadratic time, and we use this fact to construct a fast secure pseudorandom bit generator.

In \cite{GV95}, we discover by computer experiments that type II optimal normal basis generators always have high orders and are often primitive.  This has been partially verified by von zur Gathen and Shparlinski (1995) where they prove that the orders are at least $2^{\sqrt{2n}-2}$.  Type II optimal normal basis generators are special Gauss periods.  In \cite{GGP98}, we computed the orders of other Gauss periods.  Our experiment shows that  the same high order phenomenon still holds.  But this is yet to be confirmed by theory.  We also prove that Gauss periods can be exponentiated in quadratic time, and we use this fact to construct a fast secure pseudorandom bit generator.

In general, it is a well known open problem to give an efficient algorithm for constructing primitive elements in finite fields. There are algorithms in the literature that find a small set of elements with at least one element in the set being primitive.  Also, a random element in $\fqn$ is primitive with high probability.  However, the current methods known for testing primitivity in $\fqn$ require factoring the integer $q^n-1$ or computing discrete logarithms in $\fqn$. Both of the latter problems are not known to be done in polynomial time. In \cite{Gao97b}, we give a new method for constructing elements of provable high orders in $\fqn$ when $q$ is fixed.  By ``high orders'' we mean that the order is bigger than every polynomial in $n$ for large $n$.  This is the first result that constructs high order elements in $\fqn$ for all $n$ with any fixed $q$.

Difference sets in finite groups give  binary sequences of ideal autocorelations which are extremely useful in engineering applications (spread spectrum communications, stream cipher cryptosysmtems, code division multiple access systems, ranging, etc).  In \cite{GW93}, we present a general construction, via multipliers, of regular automorphism groups of a design developed from a difference set.  As an application, we obtain several infinite families of difference sets in non-abelian groups.  Other results on difference sets are in \cite{WGX90,WGY93}.

It is well-known that Cayley graphs have many nice properties that make them excellent candidates for interconnection networks for distributed and parallel computer systems.  We study  two important problems on Cayley graphs: computing connectivity (i.e., fault tolerance) and finding short disjoint paths from any given node to any collection of other nodes.  We introduce  in \cite{GNQ97} a new concept of disjoint ordering for any collection of finite sets.  Coupled with Hall's matching theorem, we give a necessary and sufficient condition for the existence disjoint orderings. We also give an efficient algorithm for constructing disjoint orderings.  As a consequence, we show how to find optimal disjoint paths on hypercubes, which are special Cayley graphs.

In \cite{GS98}, we show how to efficiently compute roots of polynomials over a function field of a plane curve. This improves the recent list-decoding algorithm of Sudan (1997) for algebraic codes (including Reed-Solomon codes) beyond the usual correction capability.

In the monograph \cite{ak:book}, we describe codes, designs, finite geometries, and their interconnections. The codes associated with finite geometries are members of the class of well known and frequently used generalized Reed-Muller codes. These codes have a number of convenient properties, including that established by Delsarte, Goethals and MacWilliams (1970) and Delsarte (1969), and in related papers, (see \cite{ak:chapter} for a full set of references) that the minimum weight of these codes is the block size of the geometrical design, and that the minimum-weight vectors generate the code. Thus a basis of minimum words exist, and in \cite{gaokey}, we construct an explicit basis in the case of the designs of points and hyperplanes from geometries over a prime field.

Related to the prior problem, the question arises as to whether the other generalized Reed-Muller codes are generated by their minimum words; we examine this in \cite{dingkey} where it is established exactly which of these codes are generated by their minimum words.

The codes from geometries first came to importance in applications when it was seen that the combinatorics could lead to a very effective decoding algorithm, majority-logic decoding: see Massey (1963).  The codes actually used in this algorithm are the dual codes of the codes from geometries or designs, and thus knowledge of the minimum weight of the dual code became an important issue. Such knowledge has not been established in the vast majority of cases. For the binary case, we obtain in \cite{calkeyder} the actual minimum weight for the designs from finite geometries. For the odd case, and for non-desarguesian planes, the results are sporadic, but the papers \cite{clakey,keyder,keyder1,keyder3}go some way to getting improved bounds.

Codes with large permutation groups can also be useful in applications, as described later in this proposal. Starting with well known simple groups and defining designs and codes through the primitive action of the groups will give structures that have this group in their automorphism group. In \cite{keymoo} we  have examined all such designs and some associated codes, for the Janko groups $J_1$ and $J_2$. This is ongoing work, sponsored by the NSF International Programs for collaboration with scientists in South Africa.

Polynomials of special forms arise in several applications including coding theory, pseudo-random number generation for simulation studies, fast arithmetic for finite fields, function field sieve for computing discrete logarithms, etc.

In \cite{BGL94,BGL96}, we study distribution of irreducible trinomials over $\ftwo$.  In \cite{GM94}, we establish necessary and sufficient conditions for $D_n(x,a)+ b$ to be irreducible over $\fq$, where $D_n(x,a)$ is the Dickson polynomial of degree $n$.  We also refute a conjecture of Chowla and Zassenhaus from 1968 about permutation polynomials.

In \cite{GH98},  we present a simple method for sieving smooth polynomials in function field sieves.  In \cite{GHP97}, we study distribution of irreducible polynomials of given forms. Many experimental results over $\ftwo$ are presented and compared with theoretical ones that are proved only for large finite fields.

Our main goals are to study algebraic techniques that are of critical importance  in symbolic computation and digital communications, particularly in reliable and secure transmission of information.

In the parlance of coding theory, we plan to study efficient encoding and decoding of algebaic geometric codes, particularly Hermitian codes which have the potential of replacing the currently used Reed-Solomon codes. Here solving linear systems and factoring polynomials over finite fields play important roles. In cryptography, we investigate efficient arithmetic of finite fields which is crucial in practical implementation of public-key cryptosystems that are based on finite fields and elliptic curves over finite fields.  The most powerful algorithms known (e.g. number field sieves and function field sieves) for attacking the security of these systems have to solve large systems of sparse linear equations over finite fields. We are interested in finding more efficient algorithms for solving such systems.

In the next few sections, we describe in more details of these problems and the goals we want to achieve.

Algebraic geometry codes
Factoring polynomials
Large systems of linear equations
Finite field arithmetic
Cryptography

Reed-Solomon codes are the most popular codes used in practice and they are well-suited for use with $M$-ary orthogonal signaling with $M=q$, where $q$ is the alphabet size of the code.  It is desirable to have codes whose lengths exceed their alphabet sizes. Recent breakthroughs in coding theory provide much more powerful methods for constructing good codes with longer lengths. They use deep results from algebraic geometry over finite fields.  One of the most well known constructions comes from so-called Hermitian curves (HC) defined by the equation $x^r + x = y^{r+1}$ over $\fq$ where $q=r^2$.  In term of function fields, this equation defines an Artin-Schreir extension. Garcia and Stitchenoth (1995) use a tower of Artin-Schreir extensions to construct an infinite family of good codes exceeding the Gilbert-Varshamov bound.

The minimum distance of a code is an important indicator of its error-correcting capability. Reed-Solomon codes are MDS codes and thus have optimal distance for a given $k$ and $n$.  The codes from Hermitian curves are close to being optimal. Their greatest advantage over Reed-Solomon codes, however, is that the alphabet sizes are much smaller than their lengths! The codes with $q=16$ and $q=64$ are really attractive as they provides codes with alphabet sizes and lengths suitable for future wireless communications networks.

In practice, a Reed-Solomon code performs much better than indicated by its minimum distance. One reason is that its weight spectrum is extremely skewed toward high weight. In fact, the average weight of an RS code of length $n$ is about $n-1$ and more than $90$\% of code words have weight larger than $n-3$, so relatively few code words have weight around the minimum.  Note that Reed-Solomon codes and Hermitian codes have similar construction in that the first is obtained by evaluating polynomials at points on a line and the second by evaluating polynomials at points on a curve.  It is thus widely believed that Hermitian codes also have weight spectrum comparable to that of Reed-Solomon codes and so perform much better than indicated by the minimum distance.

Little is known about the weight spectrum of Hermitian codes. Fortunately, Hermitian codes have a large permutation group as determined by Xing (1995).  This property can be explored to compute weight distribution as demonstrated by the recent work of Duursma (1999).  Duursma's method uses zeta functions of the curves, group characters and Tate pairing, among other things. Duursma did some partial computation for the case $q=16$.  It seems feasible to completely determine the weight distribution for this case. A more challenging task is to determine the weight distribution for the codes with $q=64$. Our goal is to carry out this computation.

The current best algorithms for decoding Hermitians codes due to Sakata et al.\ (1988--1998) are based on Grobner bases and a generalized Berlekamp-Massey algorithm (for 2-dimensional arrays). For a code of length $n$, this algorithm has time complexity O$(n^{7/3})$.  In comparison, Feng-Rao's algorithm based on Gauss elimination has time complexity O$(n^{3})$.  Our goal is to find a decoding method with quadratic time complexity.  To achieve this, we will combine Sakata's algorithm with the module structures which are afforded  by the large permutation groups of the Hermitian codes; see  Heegard et al.\ (1995) and Little et al.\ (1997) where an efficient encoding method is given.  Knowing the automorphism group, one can look for permutation decoding sets (``PD-sets'') as described originally in Mac{W}illiams (1964).  Originally MacWilliams found a method to find these sets for cyclic codes, giving an explicit set of group elements that would act as a PD-set, and could be applied in the general case; some other groups and codes have been studied, sometimes computationally. We plan to examine more groups and codes for these PD-sets, with the aim of obtaining theoretical results that can be applied to some classes, but also in some cases requiring more intensive computing facilities.  Some results for some small codes with a unitary group and a symplectic group acting, have already been obtained.

To improve the practical performance of codes, it is important to study algorithms for decoding beyond packing radius and in case of erasures of unreliable code symbols. The problem of so-called list-decoding is to find all code words that have distance to any received word up to a certain bound (larger than the packing radius). Algorithms for this problem have been recently developed by Sudan (1997) and others. One major step of these algorithms requires factoring polynomials. Recently, Gao and Shokrollahi (1998) significantly reduce the time for this step by an efficient root-finding algorithm. All these algorithms are still theoretical and more work is needed to make them practical. We plan to improve on this line of research. Another problem is to exploit erasures of unreliable code symbols in decoding Hermitian codes. We believe this can be solved in a fashion similar to Reed-Solomon codes.

In summary, Hermitian codes have alphabet size much smaller than their length and yet have similar desirable properties that Reed-Solomon codes have. There is great potential for Hermitian codes to outperform Reed-Solomon codes in future communications systems.  Our goal in this research is to determine their weight spectrum and develop practical decoding algorithms.  We also plan to evaluate their practical performance in a FH radio in wireless communications networks.

As hinted above, factoring polynomials is important in coding theory.  In fact, it is an ancient and fundamental problem in Mathematics and plays a basic role in all computer algebra systems such as Maple, Mathematica and Magma. It is also useful in many public-key cryptosystems and their analyses.

For univariate polynomials,  we study both practical and theoretical issues.  On the theoretical side, there is a long-standing open problem on the deterministic complexity of factoring under the extended Riemann hypothesis (ERH).  Our recent work \cite{Gao96a}suggests a promising approach using tools from combinatorial designs and finite projective geometry.  We plan to continue this line of research and eventually resolve this problem.  On the practical side, we plan to investigate ways to improve the current methods for factoring polynomials over finite fields.  As described in \cite{GG94}, Berlekamp's and Niederreiter's algorithms can be implemented by using fast linear solvers via a black box which performs fast multiplication of polynomials.  Here it is necessary to have efficient algorithms for finite field arithmetic and for solving large systems of linear equations over finite fields.

For factoring multivariate polynomials, we will investigate two approaches to improving the current methods. One is based on partial differential equations discovered by us recently \cite{Gao00}.  As mentioned above, this new method has near quadratic running time, greatly improving previous methods.  To implement this method, one needs a fast algorithm for solving large systems of linear equations.  Similar to the case of univariate polynomials, our linear system can be solved  via a black box approach.  We will study the efficiency of our method for polynomials over different fields including finite fields, number fields and complex number fields.

Another approach is based on polytopes also discovered by us recently \cite{Gao98, GL99}. This method does not work for all polynomials but is extemely fast for most polynomials, much faster than all the infallible algorithms known  including our PDE method.  Our preliminary implementation in \cite{GL00b} on absulute irreducibility test of multivariate polynomials have already verified this. Our next goal is to study this method for factoring polynomials. This method is expected to outperform methods based on Hensel lifting which are exponential in the worse case but fast for most polynomials. (Interestingly, we proved recently in [GaL00a] that Hensel lifting based algorithms for factoring bivariate polynomials over finite fields actually have an average running time close to linear, which explains for the first time why Hensel lifting methods are efficient in practice.)

Large systems of linear equations over finite fields arise not only in coding theory and  factoring polynomials of high degrees  but also in several other important applications including computing discrete logarithms in finite fields and factoring large integers.  The last two problems are well known to be hard and form the security foundation of many public-key cryptosystems currently used in internet communications, e-commerce and bank transactions.  The most powerful methods known to solve the two problems are based on number field sieves  and function field sieves.  A major step of these methods  needs to solve a large system of linear equations. The system is explicitly given and is extremely sparse. So a matrix-vector product can be computed quickly. In factoring polynomials, however,  the linear system may not be sparse nor explicitly given, but a  matrix-vector product can also be computed quickly via fast multiplication of polynomials. In all cases, one may assume that an algorithm, or black box,  for computing matrix-vector products is available. Our goal is to design efficient algorithms to solve the linear system calling the box as few times as possible and using  extra storage as less as possible.

To implementing the above mentioned black boxes for factoring polynomials, we need efficient algorithms for multiplication of polynomials and also for multiplication in the field $\fq$.  Indeed, efficient arithmetic in finite fields is essential for implements many error-correcting codes and public-key cryptosystems.

Polynomial bases are commonly used for finite field arithmetic.  For high degree extension fields, however, it may be advantageous to use normal bases. One main advantage of normal bases is that squaring is almost free when $p=2$.  In \cite{GGP98, GGP96a}, we give a fast algorithm for fast multiplication under normal basis representation and show how to compute large powers of elements efficiently, which is desirable in many digital signature algorithms.

Our goal is to study field arithmetic under normal bases and polynomial bases and to implement fast algorithms for polynomial multiplication over finite fields.  This will provide a tool for the algorithms mentioned above for factoring polynomials.  It will also be useful for efficient implementation of public-key cryptosystems, particularly for elliptic curve cryptosystems.

Research interests include Advanced Encryption Standard, RSA, ellitptic curves cryptosystems, and  cryptosystems based on lattices and error-correction codes. (More details later.)