The problem of finding a nontrivial factor of a polynomial f(x) over a finite field Fq has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let n be the degree. If (n?1) has a `large' r-smooth divisor s, then we find a nontrivial factor of f(x) in deterministic poly(nrlogq) time; assuming GRH and that s=(n2r . Thus, for r=O(1) our algorithm is polynomial time. Further, for r=(loglogn) there are infinitely many prime degrees n for which our algorithm is applicable and better than the best known; assuming GRH.
展开▼
