参考: 領域計算量と時間計算量整数 の素数判定には自明な方法がある. 2, 3, , で割ってみる. 2, 3, , で割ってみる. ( は を越えない最大の整数.) 2 以外は奇数で割る. いずれにせよ に比例する回数の割算が必要である. たとえば のとき, . 計算機では 1 クロックを単位として各種の命令が実行されている. 現在の一般的な CPU の クロックは 1GHz (Hz) 程度, すなわち単位操作を一秒間に 回できる程度なので, 1クロックで1回割算ができても 秒 年程かかることになる. 程度の数の素因数分解は, もっとよいアルゴリズム を用いても困難であり, それが RSA 暗号の安全性の根拠となって いる. 素朴には, 計算量とは, ある大きさのデータに対して, 計算にどれだけ 時間 (ステップ数) あるいは領域 (メモリ量) がかかるかを示す量である. ここでいくつか曖昧な点がある. この点をもう
