Author(s)

Boris S. Verkhovsky

Computer Science Department, New Jersey Institute of Technology, Newark, USA.

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.

Homogeneous Polynomials; Toom-Cook Algorithm; Multidigit Integers; Multi-Stage Multiplication; Generalized Horner Rule; Large-Integer Multiplication

B. Verkhovsky, "Large-Integer Multiplication Based on Homogeneous Polynomials," International Journal of Communications, Network and System Sciences, Vol. 5 No. 8, 2012, pp. 437-445. doi: 10.4236/ijcns.2012.58054.