Chai Wah Wu
Linear Algebra and Its Applications
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n1.815). Previous algorithms required time θ(n2+0(1)). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field double-struck Fq with q elements, the algorithms use O(n1.815 log q) arithmetic operations in double-struck Fq. The new "baby step/giant step" techniques used in our a gorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-tirne methods for manipulating normal bases of finite fields.
Chai Wah Wu
Linear Algebra and Its Applications
George Markowsky
J. Math. Anal. Appl.
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989