Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
- 10 March 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (2), 1-40
- https://doi.org/10.1145/3505584
Abstract
Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than \( n \) over a finite field \( \mathbb {F}_q \) with \( q \) elements can be multiplied in time \( O (n \log q \log (n \log q)) \), uniformly in \( q \). Under the same hypothesis, we show how to multiply two \( n \)-bit integers in time \( O (n \log n) \); this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [22]. Our results hold in the Turing machine model with a finite number of tapes.
Keywords
This publication has 38 references indexed in Scilit:
- On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functionsActa Arithmetica, 2011
- PRIMES is in PAnnals of Mathematics, 2004
- On finding primitive roots in finite fieldsTheoretical Computer Science, 1996
- Searching for primitive roots in finite fieldsMathematics of Computation, 1992
- On fast multiplication of polynomials over arbitrary algebrasActa Informatica, 1991
- New algorithms for finding irreducible polynomials over finite fieldsMathematics of Computation, 1990
- Fast polynomial transform algorithms for digital convolutionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1980
- New algorithms for digital convolutionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1977
- The fast Fourier transform in a finite fieldMathematics of Computation, 1971
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965