Large-Integer Multiplication Based on Homogeneous Polynomials
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.
Cite this paper: 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.
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.

Top