Deterministic polynomial factoring via Grobner Bases
Shuhong Gao (Clemson University)
--------------------------------------------------------------------------

While it has long been established that univariate polynomials over finite      
fields can be factored by probabilistic algorithms in polynomial time, it       
is still open whether there exists a deterministic polynomial time              
algorithm  even for simple polynomials of the form x^2-a over GF(p).            
By assuming ERH (Extended Riemann Hypothesis), several classes of               
polynomials, including quadratic polynomials, can be factored in                
deterministic polynomial time. The  question is whether ERH would allow us      
to design a deterministic polynomial time algorithm for all univariate          
polynomials  over finite fields. In this talk, we shall give a brief survey     
on the progress, including a recent approach using Grobner bases that
is joint work with Yinhua Guan.