Academic Journals Database
Disseminating quality controlled scientific knowledge

Large-Integer Multiplication Based on Homogeneous Polynomials

Author(s): Boris S. Verkhovsky

Journal: International Journal of Communications, Network and System Sciences
ISSN 1913-3715

Volume: 05;
Issue: 08;
Start page: 437;
Date: 2012;
Original page

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

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.

Tango Jona
Tangokurs Rapperswil-Jona

     Affiliate Program