论文标题
带有chudnovsky型算法的有限领域的乘法在投影线上
Multiplication in finite fields with Chudnovsky-type algorithms on the projective line
论文作者
论文摘要
我们根据d.v的方法提出了任何有限字段$ \ mathbb {f} _ {q^n} $中乘法算法的递归多项式通用结构（RPGC）。和G.V. Chudnovsky专门从事投影线。它们通常是小型扩展中的多项式插值算法，而Karatsuba算法被视为这种结构的特殊情况。使用这种算法的显式家族，我们表明它们的双线性复杂性相对于扩展程度N是准线性的，并且我们对这种复杂性产生了统一的结合。我们还证明，这些算法的构建是确定性的，可以在多项式时间内完成。我们为其构造的复杂性提供了渐近界。
We propose a Recursive Polynomial Generic Construction (RPGC) of multiplication algorithms in any finite field $\mathbb{F}_{q^n}$ based on the method of D.V. and G.V. Chudnovsky specialized on the projective line. They are usual polynomial interpolation algorithms in small extensions and the Karatsuba algorithm is seen as a particular case of this construction. Using an explicit family of such algorithms, we show that their bilinear complexity is quasi-linear with respect to the extension degree n, and we give a uniform bound for this complexity. We also prove that the construction of these algorithms is deterministic and can be done in polynomial time. We give an asymptotic bound for the complexity of their construction.
