Go
Back to the Main Page
|
|
|
|
|
|
|
|
|
|
[Gao01a]
Shuhong Gao,
``On the deterministic complexity of polynomial factoring,''
J. Symbolic Computation 31 (2001), 19--36.
Abstract:
The paper focuses on the deterministic complexity of factoring polynomials
over finite fields assuming the extended Riemann hypothesis (ERH).
By the works of Berlekamp (1967, 1970) and Zassenhaus (1969), the general
problem reduces deterministically in polynomial time to finding a proper
factor of any squarefree and completely splitting polynomial over a prime
field $\fp$. Algorithms are designed to split such polynomials.
It is proved that a proper factor of a polynomial can be found deterministically
in polynomial time, under ERH, if its roots do not satisfy some stringent
condition, called {\em super square balanced}. It is conjectured
that super square balanced polynomials do not exist.
Click
here for gzipped PS file (680k)
Click
here for PDF file (238k)