Karatsuba算法是一种快速相乘算法，它由Anatolii Alexeevitch Karatsuba于1960年提出并于1962年发表。它将两个n位数字相乘所需的一位数乘法次数减少到了至多（如果n是2的乘方，则正好为）。因此它比要n次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（n = 1024 = 2），Karatsuba算法需要3 = 59,049次个位数乘法，而经典算法需要（2） = 1,048,576次。Toom–Cook算法是此算法更快速的泛型。对于充分大的n（n >> 1）,Schönhage–Strassen algorithm算法甚至更快，算法的时间复杂度为

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most single-digit multiplications in general (and exactly when n is a power of 2). It is therefore faster than the classical algorithm, which requires n single-digit products. For example, the Karatsuba algorithm requires 3 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 2), whereas the classical algorithm requires (2) = 1,048,576.