The Karatsuba integer middle product

详细信息	查看全文 | 推荐本文 |

• 作者：David Harvey¹ ; ² ; ^{d.harvey@unsw.edu.au} ;
• 关键词：Middle product ; Integer arithmetic ; Efficient algorithm
• 刊名：Journal of Symbolic Computation
• 出版年：2012
• 期刊代码：140_07477171
• 类别：cp
• 出版时间：August, 2012
• 卷：47
• 期：8
• 页码：954-967
• 文件大小：371 K

摘要

We study the problem of computing middle products of multiple-precision integers. In particular we adapt the Karatsuba polynomial middle product algorithm to the integer case, showing how to efficiently mitigate the failure of bilinearity of the integer middle product noted by Hanrot, Quercia and Zimmermann.