Martin C. Gutzwiller
Physica D: Nonlinear Phenomena
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.
Martin C. Gutzwiller
Physica D: Nonlinear Phenomena
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Minghong Fang, Zifan Zhang, et al.
CCS 2024
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004