Guo, Zeyu and Narayanan, Anand Kumar and Umans, Chris (2016) Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics. Dagstuhl Publishing , Wadern, Germany, Art. No. 47. ISBN 9783959770163. https://resolver.caltech.edu/CaltechAUTHORS:20191118-103356388
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution. 565kB |
|
PDF
- Submitted Version
See Usage Policy. 264kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191118-103356388
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² 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.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 2016 Zeyu Guo, Anand Kumar Narayanan and Chris Umans; licensed under Creative Commons License CC-BY. The authors were supported by NSF grant CCF 1423544 and a Simons Foundation Investigator grant. | |||||||||
| Funders: |
| |||||||||
| Subject Keywords: | Algorithms, Complexity, Finite Fields, Polynomials, Factorization | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics | |||||||||
| Classification Code: | 1998 ACM Subject Classification: F.2.1 Computations in Finite Fields | |||||||||
| DOI: | 10.4230/LIPIcs.MFCS.2016.47 | |||||||||
| Record Number: | CaltechAUTHORS:20191118-103356388 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20191118-103356388 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 99898 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 18 Nov 2019 18:46 | |||||||||
| Last Modified: | 16 Nov 2021 17:50 |
Repository Staff Only: item control page
