整数を素因数分解する
素因数分解は、数を素因数の積に分解します。試し割り法、Pollard のロー法、そして素因数分解が難しい理由を学びましょう。
- 1
整数の素因数分解は素因数を見つけます:60 = 2^2 × 3 × 5。手法:試し割り(sqrt(n) までのすべての素数を試す)、Pollard の rho 法(ランダムウォークで小さい因数を高速に発見)、Pollard の p-1 法(p-1 が滑らかな場合)、数体ふるい法と GNFS(大きな数)。素因数分解は困難と考えられており(多項式時間の古典アルゴリズムなし)、これが RSA の安全性の基礎です。
- 2 約数計算ツール →
整数を素因数分解します。ツールは小〜中規模の数を効率的に処理します。大きな数(10^20 超)では分解が非常に遅くなります。これは想定どおりで、大きな鍵の RSA が安全である理由です。
- 3 最大公約数計算ツール →
GCD を分解の補助として使います。gcd(n, m) > 1 なら、n の因数を 1 つ発見したことになります。Pollard の p-1 法などの分解アルゴリズムで使われます。GCD は大きな数でも高速です(ユークリッドの互除法、O(log n))。
よくある質問
- なぜ素因数分解は難しいのですか?
- 整数の素因数分解に対する多項式時間の古典アルゴリズムは知られていません。最良のアルゴリズム(GNFS)でも準指数的計算量です。2048 ビットの RSA 鍵(2 つの 1024 ビット素数の積)の分解は、現在の技術では実行不可能です。量子コンピュータ(Shor のアルゴリズム)なら多項式時間で分解でき、RSA への脅威ですが、大規模な量子コンピュータはまだ存在しません。
- Pollard の rho 法とは何ですか?
- 法 n のランダムウォークを利用した確率的な素因数分解アルゴリズムです。p を最小の素因数として O(sqrt(p)) で因数を見つけます。小さい因数を持つ数に対しては試し割りよりはるかに高速です。ランダムウォーク内の衝突(誕生日パラドックス)を見つけ、GCD で因数を取り出す仕組みです。