Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
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.
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998