@article{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.},
    Address = {New York, NY, USA},
    Author = {Harvey, David and van der Hoeven, Joris},
    File = {Polynomial multiplication over finite fields in time O(n log n) - ffnlogn - a.pdf},
    ISSN = {0004-5411},
    Journal = {J. ACM},
    Keywords = {finite field, FFT, Polynomial multiplication, algorithm, integer multiplication, complexity bound},
    Month = {mar},
    Number = {2},
    Publisher = {Association for Computing Machinery},
    Title = {Polynomial Multiplication over Finite Fields in Time O(n log n )},
    URL = {https://doi.org/10.1145/3505584},
    Volume = {69},
    Year = {2022},
    articleno = {12},
    bdsk-url-1 = {https://doi.org/10.1145/3505584},
    date-added = {2023-02-01 20:27:13 +0100},
    date-modified = {2023-02-02 08:12:53 +0100},
    issue_date = {April 2022},
    numpages = {40},
    doi = {10.1145/3505584}
}

@article{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.}, Address = {New York, NY, USA}, Author = {Harvey, David and van der Hoeven, Joris}, File = {Polynomial multiplication over finite fields in time O(n log n) - ffnlogn - a.pdf}, ISSN = {0004-5411}, Journal = {J. ACM}, Keywords = {finite field, FFT, Polynomial multiplication, algorithm, integer multiplication, complexity bound}, Month = {mar}, Number = {2}, Publisher = {Association for Computing Machinery}, Title = {Polynomial Multiplication over Finite Fields in Time O(n log n )}, URL = {https://doi.org/10.1145/3505584}, Volume = {69}, Year = {2022}, articleno = {12}, bdsk-url-1 = {https://doi.org/10.1145/3505584}, date-added = {2023-02-01 20:27:13 +0100}, date-modified = {2023-02-02 08:12:53 +0100}, issue_date = {April 2022}, numpages = {40}, doi = {10.1145/3505584} }