Karatsuba

カラツバ法（Karatsuba algorithm）とは、2つの大きな数を乗算する場合に、従来の方法よりも効率的なアルゴリズムです。このアルゴリズムは、分割統治法を基本原則としています。

通常の乗算アルゴリズムでは、N桁の数を掛ける場合には、O(n^2)の時間が必要です。 一方、カラツバ法を用いると、O(n^log_23)の時間で乗算を行うことができます。このアルゴリズムは、大きな数を扱う暗号技術などで広く使用されています。