Large-Integer Multiplication Based on Homogeneous Polynomials

• 作者: Boris S. Verkhovsky
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: Homogeneous POLYNOMIALS Toom-Cook Algorithm Multidigit INTEGERS MULTI-STAGE MULTIPLICATION Generalized Horner Rule Large-Integer MULTIPLICATION
• 年，卷（期）: 2012,（8）
• 页码范围: 437-445
• 页数: 9页
• 分类号: O1

摘要

Several algorithms based on homogeneous polynomials for multiplication of large integers are described in the paper. The homogeneity of polynomials provides several simplifications: reduction of system of equations and elimination of necessity to evaluate polynomials in points with larger coordinates. It is demonstrated that a two-stage implementation of the proposed and Toom-Cook algorithms asymptotically require twice as many standard multiplications than their direct implementation. A multistage implementation of these algorithms is also less efficient than their direct implementation. Although the proposed algorithms as well as the corresponding Toom-Cook algorithms require numerous algebraic additions, the Generalized Horner rule for evaluation of homogeneous polynomials, provided in the paper, decrease this number twice.