TITLE:
Large-Integer Multiplication Based on Homogeneous Polynomials
AUTHORS:
Boris S. Verkhovsky
KEYWORDS:
Homogeneous Polynomials; Toom-Cook Algorithm; Multidigit Integers; Multi-Stage Multiplication; Generalized Horner Rule; Large-Integer Multiplication
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.5 No.8,
August
28,
2012
ABSTRACT: 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.