A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by $n$, the algorithm uses $O(n^{1.43})$ field operations, breaking through the $3/2$ barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require $O(n^{1.63})$ field operations in general, and ${n^{3/2+o(1)}}$ field operations in the particular case of power series over a field of large enough characteristic. If using cubic-time matrix multiplication, the new algorithm runs in ${n^{5/3+o(1)}}$ operations, while previous ones run in $O(n^2)$ operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.
翻译：一种新的拉斯维加斯算法, 用于组成两个多数值模型, 一个是任意的字段。 当这些多数值序列的温度受美元约束时, 该算法首次使用美元( {{{{1.43}}) 美元实地操作, 首次突破Expent 中的3/2美元屏障。 1978年布伦特 和 Kung 导致的上一个最快的代数算法, 通常需要美元( {n} 1. 63} 美元) 的实地操作, 以及 ${n}3/2+o(1)} $ 实地操作, 在一个足够高特性的域的电源序列中, 需要美元( { n}3/2+(1)} 美元) 。 如果使用立方位矩阵乘法, 新的算法运行以${ {n} 5/3+ ⁇ 1} 美元运行, 而前一个算法则是 $( {n} 2) 。 我们的方法依赖于计算一个典型的微大小的代数关系矩阵。 。 随机化是用来减少这种有利情况的任意输入 。
相关内容
微信扫码咨询专知VIP会员