計算速度
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/07 01:28 UTC 版)
最悪計算量を考えると、試し割り法は非常に時間のかかるアルゴリズムである。2進法でのn桁の数aに対して、2から順にaの平方根まで試すアルゴリズムは π ( 2 n / 2 ) ≈ 2 n / 2 ( n 2 ) ln 2 {\displaystyle \pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}} 回の割り算を行う。 ここで、 π ( x ) {\displaystyle \pi (x)} は素数計数関数であり、x未満の素数の数である。これは約数の候補として素数を取得する素数判定のオーバヘッドを説明しきるものではない。便利なテーブルはそこまで大きくなく、符号つき16ビット整数の範囲内の最大の素数であればP(3512)=32749、符号なし16ビット整数の範囲内での最大の素数であればP(6542)=65521である。 このテーブルを使うことによって、655372 =4,295,098,369までの素数判定が可能である。このようなテーブルはエラトステネスの篩でも用いられ、大規模な素数判定には有用であるが、その一方で単純に2とnの平方根以下の奇数のみで素数判定を行う手法も存在する。その場合には、n桁の数を判定するためにかかる計算はおよそ 2 n / 2 {\displaystyle 2^{n/2}} である。両者とも、計算時間は桁数に対して指数関数的に増加する。 このように試し割り法は非常に時間がかかるアルゴリズムではあるが、最も効率の良い手法でも計算時間が桁数に対して指数関数的に増加するため、十分満足できる手法である。与えられた範囲の整数に対して素数判定をする場合、2で割り切れる確率は50%であり、3で割り切れる確率は約33%であり、88%の自然数は100未満の約数を持つ、92%の自然数は1000未満の約数を持つ。したがって、大きな整数aの素数判定を行う場合小さな素数で割り切れるかを確かめることは有用である。 しかし、小さな素数を約数として持たない巨大な数の素数判定は数日もしくは数カ月もかかる場合がある。そのような場合には、二次ふるい法や一般数体ふるい法（GNFS）のような他の手法が用いられる。しかし、これらの方法の（時間）計算量も超多項式時間であるため、実用上の限界は比較的すぐにやってくる。この性質を利用して、解読に素因数分解が必要である公開鍵暗号方式で素数の積が用いられる。公開鍵暗号ではスーパーコンピュータやグリッド・コンピューティングを用いても既知の素因数分解アルゴリズムでは実用的な時間で素因数分解できない大きさの素数の積を用いている。今までに素因数分解された暗号の最大の桁数は RSA-768 の768ビットであり、数百台の計算機で一般数体ふるい法を用いて、およそ2年の計算の結果、素因数分解された。
※この「計算速度」の解説は、「試し割り法」の解説の一部です。
「計算速度」を含む「試し割り法」の記事については、「試し割り法」の概要を参照ください。
「計算速度」の例文・使い方・用例・文例
- 計算速度のページへのリンク
