整数 の素数判定には自明な方法がある.
程度の数の素因数分解は, もっとよいアルゴリズム
を用いても困難であり, それが RSA 暗号の安全性の根拠となって
いる.
素朴には, 計算量とは, ある大きさのデータに対して, 計算にどれだけ 時間 (ステップ数) あるいは領域 (メモリ量) がかかるかを示す量である. ここでいくつか曖昧な点がある. この点をもうすこし詳しく考察しよう.
![]()
for (;
;
++ )
![]()
![]()
![]()
end for![]()
この計算で, かけ算は 回, 10 による割算が
回必要である.
次に, をシフトして足していく計算を考える.
これは, 繰り上がりを無視すれば
桁の数
,
の加算と考えてよいから次のアルゴリズムで計算できる.
![]()
for (;
;
++ )
![]()
if![]()
,
![]()
else,
![]()
end for
(繰り上がりの処理)
これは, 本質的には加算が 回で計算できる.
以上の計算が
回必要になるから,
桁の数の積の計算には
に比例するステップ数が必要になることが分かる.
桁の整数を二つかける筆算アルゴリズムの計算量は
であった.
このアルゴリズムはさらに改良可能である.
簡単な高速化アルゴリズムとして, Karatsuba アルゴリズムを紹介する.
まず, 二桁の数
の積を考える.
普通にやると
なお,
一変数多項式の積でも同じアルゴリズムが使える. かなり低い次数
(20 次程度) から, 通常の アルゴリズムより高速になる.