Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
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.
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering