Name
Title | ||
|---|---|---|
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. |
Abstract | ||
|---|---|---|
The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) time to factor polynomials of degree n over the finite field F_q with q elements. A significant open problem is if the 3/2 exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than 3/2 would yield an algorithm for polynomial factorization with exponent better than 3/2. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4230/LIPIcs.MFCS.2016.47 | mathematical foundations of computer science |
DocType | Volume | Citations |
Conference | abs/1606.04592 | 0 |
PageRank | References | Authors |
0.34 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zeyu Guo | 1 | 0 | 0.34 |
| Anand Kumar Narayanan | 2 | 11 | 4.00 |
| Christopher Umans | 3 | 879 | 55.36 |