Fast Algorithm for Factoring Polynomials over Finite Fields
Ke Shan · Journal of Information Engineering University · 2003
A probabilistic algorithm for factoring univariate polynomials over finite fields is presented.To factor a polynomial of degree n over Fq,the number of arithmetic operations in Fq is O(n~(ω(1,3/4,3/4))+n~(1+o(1))logq).The main idea comes from Kaltofen Shoup's algorithm.