Large-Integer Multiplication Based on Homogeneous Polynomials

Boris S. Verkhovsky

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

DOI: 10.4236/ijcns.2012.58054                

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.

Keywords

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. Karatsuba and Yu. Ofman, “Multiplication of Multidigit Numbers on Automata,” Soviet Physics-Doklady, Vol. 7, 1963, pp. 595-596.
[2]	A. Toom, “The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers,” Soviet Mathematics-Doklady, Vol. 7, 1963, pp. 714-716.
[3]	S. A. Cook, “On the Minimum Computation Time of Functions,” Chapter 3, Ph.D. Thesis, Harvard University, Cambridge, 1966, pp. 51-77.
[4]	D. Knuth, “Art of Computer Programming: Seminumerical Algorithms,” 2nd Edition, Vol. 2, Addison-Wesley, New York, 1981.
[5]	R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, New York, 2001. doi:10.1007/978-1-4684-9316-0
[6]	D. Bernstein, “Multidigit Modular Multiplication with Explicit Chinese Remainder Theorem,” 1997. ftp://koobera. math.uic.edu/pub/papers/m3.dvi
[7]	R. Crandall, “Method and Apparatus for Public Key Exchange in a Cryptographic Systems,” US Patents 5159632, 1992; 5271061, 1993; 5463690, 1994.
[8]	F. Ablayev and M. Karpinski, “A Lower Bound for Integer Multiplication on Randomized Ordered Read-once Branching Programs,” Information and Computation, Vol. 186, No. 1, 2003, pp. 78-89. doi:10.1016/S0890-5401(03)00118-4
[9]	A. Zanoni, “Iterative Toom-Cook Methods for Very Unbalanced Long Integer Multiplication,” Proceedings of the 2010th International Symposium on Symbolic and Algebraic Computation, Munich, 25 July 2010, pp. 319-323. doi:10.1145/1837934.1837995
[10]	W. G. Horner, “A New Method of Solving Numerical Equations of All Orders, by Continuous Approximation,” Philosophical Transactions of Royal Society of London, Vol. 109, 1819, pp. 308-335. doi:10.1098/rstl.1819.0023
[11]	B. Verkhovsky and R. Rubino, “Corporate Intranet Security: Packet-Level Protocols for Preventing Leakage of Sensitive Information and Assuring Authorized Network Traffic,” International Journal of Communications, Network and System Sciences, Vol. 5, No. 5, 2012, pp. 517- 524.