Related Concepts
Definition
A method for multiplying two polynomials that saves coefficient multiplications at the cost of extra additions compared to the schoolbook multiplication method.
Theory
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...
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Bernstein DJ (2001) Multidigit multiplication for mathematicians. Accepted to Advances in Applied Mathematics, but withdrawn by author. Available at http://cr.yp.to/papers.html#m3.
Erdem SS (2001) Improving the Karatsuba-Ofman multiplication algorithm for special applications. PhD thesis, Department of Electrical & Computer Engineering, Oregon State University, 8 Nov 2001
Karatsuba A, Ofman Y (1963) Multiplication of multidigit numbers on automata. Sov Phys Dokl 7:595–596
Knuth DE (1997) The art of computer programming, vol 2: Seminumerical algorithms, 3rd edn. Addison-Wesley, Reading, Massachusetts
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, Paar C (2002) Generalizations of the Karatsuba algorithm for efficient implementations. Technical Report, Ruhr-University Bochum. Available at http://www.crypto.rub.de
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer Science+Business Media, LLC
About this entry
Cite this entry
Weimerskirch, A. (2011). Karatsuba Algorithm. In: van Tilborg, H.C.A., Jajodia, S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_35
Download citation
DOI: https://doi.org/10.1007/978-1-4419-5906-5_35
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4419-5905-8
Online ISBN: 978-1-4419-5906-5
eBook Packages: Computer ScienceReference Module Computer Science and Engineering