Rings of Low Multiplicative Complexity
Rings of Low Multiplicative Complexity
复制标题
低乘法复杂度环
DOI：
10.1006/ffta.1999.0270
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. Silverman
中科院分区：
文献类型：
--
作者：
J. Silverman
有限域中乘法运算的复杂性出于理论和实践的原因而引起人们的关注。例如，F2N 的最佳正态基的复杂度为 2N?1。 J. H. Silverman（“加密硬件和嵌入式系统”，计算机科学讲义，第 1717 卷，第 122-134 页，Springer？Verlag，柏林，1999 年）中描述的构造允许通过在 F2 上维度为 N+1 的较大环 R 中工作，在 F2N 中执行复杂性 N+1 的乘法。在本文中，我们给出了所有此类环的完整分类，并表明这种结构是唯一还具有一定有用的可置换性的结构。
The complexity of the multiplication operation in finite fields is of interest for both theoretical and practical reasons. For example, an optimal normal basis for F2N has complexity 2N?1. A construction described in J. H. Silverman, (“Cryptographic Hardware and Embedded Systems,” Lecture Notes in Computer Science, Vol. 1717, pp. 122?134, Springer?Verlag, Berlin, 1999.) allows multiplication of complexity N+1 to be performed in F2N by working in a larger ring R of dimension N+1 over F2. In this paper we give a complete classification of all such rings and show that this construction is the only one which also has a certain useful permutability property.