素因数分解 【prime factorization】
概要
素因数分解（prime factorization）とは、ある正の整数を、素数の積(掛け算)の形で表すこと。例えば、60を素因数分解すると 22×3×5 と表すことができる。1と素数以外の正の整数は合成数と呼ばれ、1と自身以外の約数を持つ。合成数は複数の素数（素因数）を掛け合わせた形に分解することができ、その結果から、（正の）約数の数を求めたり、すべて列挙することができる。素因数分解の仕方（素因数の組み合わせ）は一通りしか無い。
素因数分解の方法は、基本的には元の数が各素数で割り切れるか順に試してみるしかなく、素因数の候補を絞り込む手法は提唱されているが、桁数が増えても一定の短い手順で分解する方法は発見されていない。ただし、素因数が最も大きくなるのは同じ大きさの素因数2つに分解できる場合であるため、探索する素数は元の数の平方根までで良い。
数百桁のような巨大な素数2つを乗算して合成数を求めるのは容易である一方、その合成数から2つの巨大な素因数を見つけるのは現代数学の絞り込み技法と現代のコンピュータの計算能力を駆使しても途方もない時間がかかることが知られている。この素因数分解の困難性は、世界で初めて考案された公開鍵暗号であるRSA暗号に応用されている。
(2023.11.13更新)
共有ボタンをタップ