Generalizations of the Karatsuba Algorithm for Efficient Implementations
Generalizations of the Karatsuba Algorithm for Efficient Implementations
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
A. Weimerskirch;C. Paar
中科院分区：
文献类型：
--
作者：
A. Weimerskirch;C. Paar
在这项工作中，我们将经典的多项式乘法Karatsuba算法（KA）推广到（i）任意次数的多项式和（ii）递归使用。我们确定精确的复杂性表达式KA和专注于如何使用它与最少的操作。我们开发了一个规则的步骤的最佳顺序，如果KA递归使用。我们展示了如何使用虚拟系数可以提高性能。最后，我们提供详细的信息，如何使用KA的成本最低，也提供了表格，描述了最好的可能使用的多项式KA的次数为127。我们的研究结果是特别有用的高效实现的密码和编码方案在固定大小的字段，如GF（p）。
In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127. Our results are especially useful for efficient implementations of cryptographic and coding schemes over fixed-size fields like GF (p).