Polynomial Multiplication over Finite Fields in Time ( O(n log n )
Polynomial Multiplication over Finite Fields in Time ( O(n log n )
复制标题
时间有限域上的多项式乘法 ( O(n log n )
DOI：
--
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
J. van der Hoeven
中科院分区：
文献类型：
--
作者：
David Harvey;J. van der Hoeven
假设一个被广泛相信的关于算术级数中的最小素数的假设，我们证明了有限域（mathbb {F}_q）上具有（q）个元素的次数小于（n）的多项式可以在时间上相乘（O（n log q log（n log q），在（q）中一致。在相同的假设下，我们展示了如何在时间上乘以两个（n）位整数（O（n log n））;该算法比配套论文[22]中的无条件算法稍微简单一些。我们的结果在有限数量磁带的图灵机模型中成立。
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.