Kedlaya, Kiran S. and Umans, Christopher
(2008)
*Fast Modular Composition in any Characteristic.*
In:
2008 49th Annual IEEE Symposium on Foundations of Computer Science.
IEEE
, Piscataway, NJ, pp. 146-155.
ISBN 978-0-7695-3436-7.
https://resolver.caltech.edu/CaltechAUTHORS:20191126-160438923

PDF
- Published Version
See Usage Policy. 335kB |

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191126-160438923

## Abstract

We give an algorithm for modular composition of degree n univariate polynomials over a finite field F_q requiring n^(1 + o(1))log^(1 + o(1))q bit operations; this had earlier been achieved in characteristic n^(o(1)) by Umans (2008). As an application, we obtain a randomized algorithm for factoring degree n polynomials over F_q requiring (n^(1.5 + o(1)) + n^(1 + o(1)) log q) log^(1 + o(1)) q bit operations, improving upon the methods of von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998). Our results also imply algorithms for irreducibility testing and computing minimal polynomials whose running times are best-possible, up to lower order terms.As in Umans (2008), we reduce modular composition to certain instances of multipoint evaluation of multivariate polynomials. We then give an algorithm that solves this problem optimally (up to lower order terms), in arbitrary characteristic. The main idea is to lift to characteristic 0, apply a small number of rounds of multimodular reduction, and finish with a small number of multidimensional FFTs. The final evaluations are then reconstructed using the Chinese Remainder Theorem. As a bonus, we obtain a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithm uses techniques which are commonly employed in practice, so it may be competitive for real problem sizes. This contrasts with previous asymptotically fast methods relying on fast matrix multiplication.

Item Type: | Book Section | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||

Additional Information: | © 2008 IEEE. Supported by NSF DMS-0545904 (CAREER) and a Sloan Research Fellowship. Supported by NSF CCF-0346991, BSF 2004329, a Sloan Research Fellowship, and an Okawa Foundation research grant. We thank Swastik Kopparty and Madhu Sudan for some references mentioned in Section 4, and Ronald deWolf and the FOCS 2008 referees for helpful comments. | ||||||||||||

Funders: |
| ||||||||||||

DOI: | 10.1109/focs.2008.13 | ||||||||||||

Record Number: | CaltechAUTHORS:20191126-160438923 | ||||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20191126-160438923 | ||||||||||||

Official Citation: | K. S. Kedlaya and C. Umans, "Fast Modular Composition in any Characteristic," 2008 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 2008, pp. 146-155. doi: 10.1109/FOCS.2008.13 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 100081 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Tony Diaz | ||||||||||||

Deposited On: | 27 Nov 2019 00:13 | ||||||||||||

Last Modified: | 16 Nov 2021 17:51 |

Repository Staff Only: item control page