A Caltech Library Service

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

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.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Guo, Zeyu0000-0001-7893-4346
Narayanan, Anand Kumar0000-0002-0106-030X
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.
Funding AgencyGrant Number
Simons FoundationUNSPECIFIED
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
Record Number:CaltechAUTHORS:20191118-103356388
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99898
Deposited By: Tony Diaz
Deposited On:18 Nov 2019 18:46
Last Modified:16 Nov 2021 17:50

Repository Staff Only: item control page