Large-Integer Multiplication Based on Homogeneous Polynomials
- 1 Computer Science Department, New Jersey Institute of Technology, Newark, USA
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.
- A. Karatsuba and Yu. Ofman, “Multiplication of Multidigit Numbers on Automata,” Soviet Physics-Doklady, Vol. 7, 1963, pp. 595-596.
- A. Toom, “The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers,” Soviet Mathematics-Doklady, Vol. 7, 1963, pp. 714-716.
- S. A. Cook, “On the Minimum Computation Time of Functions,” Chapter 3, Ph.D. Thesis, Harvard University, Cambridge, 1966, pp. 51-77.
- D. Knuth, “Art of Computer Programming: Seminumerical Algorithms,” 2nd Edition, Vol. 2, Addison-Wesley, New York, 1981.
- R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, New York, 2001. doi:10.1007/978-1-4684-9316-0
- D. Bernstein, “Multidigit Modular Multiplication with Explicit Chinese Remainder Theorem,” 1997. ftp://koobera. math.uic.edu/pub/papers/m3.dvi
- R. Crandall, “Method and Apparatus for Public Key Exchange in a Cryptographic Systems,” US Patents 5159632, 1992; 5271061, 1993; 5463690, 1994.
- 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
- 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
- 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
- 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.