The Karatsuba algorithm (KA) for multiplying two polynomials was introduced in 1962 [3]. It saves coefficient multiplications at the cost of extra additions compared to the schoolbook or ordinary multiplication method. The basic KA is performed as follows. Consider two degree-1 polynomials \(A(x)\) and \(B(x)\) with \(n=2\) coefficients:
Let \(D_0, D_1, D_{0,1}\) be auxiliary variables with
Then the polynomial \(C(x) = A(x) B(x)\) can be calculated in the following way:
This method requires three multiplications and four additions. The schoolbook method requires \(n^2\) multiplications and \((n-1)^2\) additions, i.e., four multiplications and one addition. Clearly, the KA can also be used to multiply integer numbers.
The KA can be generalized for polynomials of arbitrary degree [6]. The following algorithm describes a method to multiply two arbitrary polynomials with n coefficients using the one-iteration KA.
Algorithm 1....
This is a preview of subscription content, log in via an institution to check access.
References
Bernstein, D.J. (1998). “Multidigit multiplication for mathematicians.” to appear in Advances in Applied Mathematics.
Erdem, S.S. (2001). “Improving the Karatsuba–Ofman multiplication algorithm for special applications.” PhD Thesis, Department of Electrical & Computer Engineering, Oregon State University.
Karatsuba, A. and Y. Ofman (1963). “Multiplication of multidigit numbers on automata.” Sov. Phys.—Dokl., 7, 595–596.
Knuth, D.E. (1997). The Art of Computer Programming. Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, Reading, MA.
Paar, C. (1994). “Efficient VLSI architecture for bit parallel computation in Galois fields.” PhD Thesis, Institute for Experimental Mathematics, University of Essen, Germany.
Weimerskirch, A. and C. Paar (2002). “Generalizations of the Karatsuba algorithm for efficient Implementations.” Technical Report, Ruhr-University Bochum, 2002. Available at http://www.crypto.rub.de
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 International Federation for Information Processing
About this entry
Cite this entry
Weimerskirch, A. (2005). Karatsuba algorithm. In: van Tilborg, H.C.A. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA . https://doi.org/10.1007/0-387-23483-7_214
Download citation
DOI: https://doi.org/10.1007/0-387-23483-7_214
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-23473-1
Online ISBN: 978-0-387-23483-0
eBook Packages: Computer ScienceReference Module Computer Science and Engineering