2026-07-24T10:09:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6460 2024-03-06T10:38:20Z ddc:004 open_access

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields Guo, Zeyu Narayanan, Anand Kumar Umans, Chris algorithms complexity finite fields polynomials factorization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeyu Guo and Anand Kumar Narayanan and Chris Umans 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.47 urn:nbn:de:0030-drops-64609 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.47 eng https://creativecommons.org/licenses/by/3.0/legalcode