Knuth[S2]によれば、この算法がはじめて公表されたのは、1962年に当時のソ連のKaratsubaが発表した論文によるそうです。Knuth自身はこれをディジタル法と名付けています。

　２つの多倍長整数が基数P>0によって次のように表現されているとします。この積を計算します。この最後の式からこの計算には4回の積と3回の和と桁上げ処理が必要なことがわかります。ところがここで、とおくとが成り立ちます。この場合は3回の積と4回の和と2回の差と桁上げ処理になります。つまり1回の積を1回の和と2回の差に置き換えたことになります。さらに、とおくとが成り立ちます。この場合も3回の積と4回の和と2回の差と桁上げ処理になります。

　前者は、例えば２進計算機が32bitの演算器を持つときに、基数P=2³²として倍精度の乗算に適用することができます。後者は、t₁の計算の途中で負の値がでてくることはありませんので、多倍長整数計算で値を絶対値表現しているときに有効です。

　まず、計算量の評価を行なうために使われる道具を導入しておきましょう。

　nビット長の多倍長整数の乗算の古典算法による計算時間(これを計算量と呼ぶ)をT_CL(n)とすると、n→∞のときとなることがわかっています。Karatsuba法の計算量T_KO(n)を評価してみましょう。加減算の計算量はn→∞のときO(n)であることから、となる定数kが存在します。T_KO(1)とkの大きい方を改めてkとおき、数列{2^r|r=0,1,…}について、と定めるとが成り立ちます。なぜならば、r=0のときは明らかで、r=nで正しいと仮定すると、となり、r=n+1でも成り立つからです(数学的帰納法)。このことからという不等式が得られます。nを任意に与えたときに、n以上で最小の2^rが存在します。このときとなっています。上の不等式を使って、ここで、と実数のべき乗の定義から導かれる等式を使うと、が導かれます。したがって次の定理が証明されました。