Abstract
Toom-Cook strategy is a well-known method for building algorithms to efficiently multiply dense univariate polynomials. Efficiency of the algorithm depends on the choice of interpolation points and on the exact sequence of operations for evaluation and interpolation. If carefully tuned, it gives the fastest algorithm for a wide range of inputs.
This work smoothly extends the Toom strategy to polynomial rings, with a focus on 
. Moreover a method is proposed to find the faster Toom multiplication algorithm for any given splitting order. New results found with it, for polynomials in characteristic 2, are presented.
A new extension for multivariate polynomials is also introduced; through a new definition of density leading Toom strategy to be efficient.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodrato, M.: Notes on Low Degree Toom-Cook Multiplication with Small Characteristic, Techniocal Report, Centro V.Volterra, Università di Roma Tor Vergata (2007)
Bodrato, M., Zanoni, A.: Integer and Polynomial Multiplication: Towards Optimal Toom-Cook Matrices. Proceedings of the ISSAC 2007 Conference. ACM press, New York (2007), http://bodrato.it/papers/#ISSAC2007
Chung, J., Anwar Hasan, M.: Asymmetric squaring formulae, Technical Report. CACR 2006-24, University of Waterloo (2006)
Cook, S.A.: On the Minimum Computation Time of Functions, Thesis, Harvard University, pp. 51–77 (1966)
The GNU Multi-Precision Library (GMP), http://gmplib.org/
The GP-Pari Computer Algebra System, http://pari.math.u-bordeaux.fr/
Hart, P.E., Nilsson, N.J., Raphael, B.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics SSC4, pp. 100–107 (1968)
Jebelean, T.: An algorithm for exact division. Journal of Symbolic Computation 15, 169–180 (1993)
Karatsuba, A., Ofman, Y.: Multiplication of multidigit numbers on automata, Soviet Physics-Doklady, 7, 595–596 (1963); translation from Dokl. Akad. Nauk SSSR, 145(2), 293–294, (1962)
Knuth, D.E.: The Art of Computer Programming (Chapter 4, Section 3.3), vol. 2, pp. 278–301. Addison-Wesley, Reading, MA (1981)
Kronecker, L.: Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal Für die Reine und Angewandte Mathematik, pp. 92–122 (1882)
The Number Theory Library (NTL), http://www.shoup.net/ntl/
Toom, A.L.: The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers. Soviet Mathematics 3, 714–716 (1963)
Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7, 281–292 (1971)
Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta. Informatica 7, 395–398 (1977)
Weimerskirch, A., Paar, C.: Generalizations of the Karatsuba Algorithm for Efficient Implementations, Cryptology ePrint Archive, Report 224 (2006)
Winograd, S.: Arithmetic Complexity of Computations, CBMS-NSF Regional Conference Series in Mathematics, vol. 33 (1980)
Zimmermann, P., Quercia, M.: Private communication, October 2006, irred-ntl source code (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodrato, M. (2007). Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In: Carlet, C., Sunar, B. (eds) Arithmetic of Finite Fields. WAIFI 2007. Lecture Notes in Computer Science, vol 4547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73074-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-73074-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73073-6
Online ISBN: 978-3-540-73074-3
eBook Packages: Computer ScienceComputer Science (R0)