Subquadratic-time factoring of polynomials over finite fields
Erich Kaltofen, Victor Shoup · 1995
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields.The algorithms factor a polynomial of de reen over afinite field of constant cardi-#8,5 nality in time O(n ).Previous algorithms required time @(n2+0(1)).Thenew algorithms rely on fast matrix multiplacation techniques.More generally, to factor a polynomial of degree noverthe finite field F~with q elements, the algo-1 Sl.510gqJ ~ithmetic operations in J?9. rithms use O(n The new "baby step/giant step" techniques used in our algorithms also yield new fast practical algorithms at superquadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields. 1