numbers 素因数分解計算ツール star

使い方

素因数分解とは、ある数をその素数の構成要素の積として表すことです — 例えば60 = 2² × 3 × 5のように。算術の基本定理は、1より大きいすべての整数がちょうど一つのこのような分解を持つこと(因数の順序の入れ替えを除いて)を保証します:60をどのような順序で割っていっても、素因数への分解は一通りしかありません。この一意性こそが、素因数分解を任意の選択ではなく、意味のある明確に定義された演算にしているのです。

このツールは試し割りによってこれを求めます:まず可能な限り2で割り(何回きっちり割れるかを数えながら)、次に3, 5, 7, 9, 11…という奇数の候補に移り、残っている数の平方根に達するまで、それぞれを可能な限り割っていきます。360を例にした計算過程:2で3回割ります(360→180→90→45、つまり2³)。次に45は奇数なので、3で2回割ります(45→15→5、つまり3²)。残った5はそれ自体が素数です(5¹)。結果:360 = 2³ × 3² × 5となり、逆に掛け合わせて確認すると — 8 × 9 × 5 — たしかに360になります。√nまでのどの候補で割っても残った数が割り切れない場合、その残りの数自体が素数であり、そこで分解は完了します。

知っておくべきこと

小さい数や中程度の数は、この方法でほぼ瞬時に分解できます。しかし同じ試し割りの手法は、数百桁にも及ぶ非常に大きな数に対しては計算量的に困難になります。確認すべき候補の数が膨大に増加するためで、古典的なコンピュータでは一般の整数に対する既知の効率的な(多項式時間の)アルゴリズムは存在しません。この非対称性 — 2つの大きな素数を掛け合わせるのは高速だが、その積を素因数に戻して分解するのは遅い — は単なる興味深い性質ではなく、RSA公開鍵暗号のまさにセキュリティの基盤です:公開鍵は2つの巨大な秘密の素数の積から作られ、暗号を破るにはその積を素因数分解する必要がありますが、現在使われている鍵のサイズではそれは事実上不可能です。

• 1にはそもそも素因数分解が存在しません — 素数でも合成数でもなく、「空の積」という慣習によって特別な場合として扱われます。
• ある数が、自身の平方根までの試し割りをすべて生き延び、何にも割り切れない場合、その数は定義上素数です。
• 暗号技術以外にも、素因数分解は分数の約分、最大公約数(GCD)と最小公倍数(LCM)を求めること、ある数の約数の個数を求めることの基盤となっています。