Fast Polynomial Factorization and Modular Composition

By Kiran S. Kedlaya, C. Umans. 2011

259 citations recorded by the source corpus.

We obtain randomized algorithms for factoring degree $n$ univariate polynomials over $F_q$ requiring $O(n^{1.5 + o(1)} log^{1+o(1)} q+ n^{1 + o(1)}log^{2+o(1)} q)$ bit operations. When $log q < n$, this is asymptotically faster than the best previous algorithms (von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998)); for $log q ge n$, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree $n$ univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use $O(n^{(omega + 1)/2})$ field operations, where $omega$ is the exponent of matrix multiplication (Brent & Kung (1978)), with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication (Huang & Pan (1997)). We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent $alpha$ implies an algorithm for the other with exponent $alpha + o(1)$, and vice versa. We then give two new algorithms that solve the problem optimally (up to lower order terms): an algebraic algorithm for fields of characteristic at most $n^{o(1)}$, and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of {em multimodular reduction}, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese Remainder Theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques which are commonly employed in practice, so they may be competitive for real problem sizes. This contrasts with all previous subquadratic algorithsm for these problems, which rely on fast matrix multiplication. This is joint work with Kiran Kedlaya.

Subfields: Artificial Intelligence, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, methodology): “Second, encoding the masked models with Lagrange coding has a computation overhead of O(logN log(2) logN log log logN), because evaluating a polynomial of degree i at any j points has a computation overhead of O(j log(2) i log log i) [47], and both i and j are logN for the encoding operation.”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, background): “It is known that both operations only require almost linear complexities: interpolating a polynomial of degree k has a complexity of O ( k log 2 k log log k ) , and evaluating it at any k points requires the same [41].”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, background): “It is well known that polynomial interpolation of degree k has a complexity of O(k log(2) k log log k) [15].”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, background): “The complexities of interpolating a degree-k polynomial and evaluating a degree-k polynomial at k points are both O ( k log 2 k log log k ) (see, e.g., [23]), hence the decoding complexity at the master of the PCR scheme is O ( d log 2 log log ) .”
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (2018, background): “It is well known that polynomial interpolation of degree k has a complexity of O(k log(2) k log log k) [16].”
Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation (2018, background): “Hereby, the complexity of a t-degree polynomial interpolation is O(t log(2) t log log t) [12].”
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication (2018, background): “[29] Kedlaya, K. S., and Umans, C. Fast polynomial factorization and modular composition.”