素因数分解 | Instrumentize

1より大きいすべての整数は素数の積であり、その積の表し方はただ1通りです。これが算術の基本定理です。このツールはその積を求め、そこから導かれるすべて、つまり約数がいくつあり、それが何かを示します。

仕組み

試し割りに、近道を1つ加えています。2と3を取り除いたあと、残りの素数はすべて6の倍数のすぐ隣にあるので、候補を2ずつではなく6ずつ進めます。ふるいを通り抜けて残ったものは素数で、最後の因数になります。

約数はn以下のすべての数を試すのではなく、素因数分解から組み立てます。2³ × 3² × 5と書ける数の約数は(3+1) × (2+1) × (1+1) = 24個で、どの約数も各素数をいくつ取るかの選び方1つに対応するので、素因数分解がわかれば一覧にするのに手間はかかりません。

上限は1兆です。試し割りは最大でその数の平方根まで進めればよく、1兆なら100万回の手順なので高速です。それを超えると、たまたま大きな素数2つの積だった数でページが1分間読み込み続けることになるため、処理を断ります。

1ではなく2から始まるのはなぜですか？

1には素因数分解がなく、1を素数と呼ぶと、この分野全体が拠って立つ一意性が崩れるからです。1が素数なら、6は2 × 3でもあり、1 × 2 × 3でも1 × 1 × 2 × 3でもあることになり、答えが1つではなくなります。0はさらに厄介で、すべての数が0を割り切ります。

ある数の約数はいくつありますか？

素因数分解の各指数に1を足して掛け合わせます。360は2³ × 3² × 5なので、4 × 3 × 2 = 24個です。素数の約数は2個（自分自身と1）で、平方数の約数は常に奇数個です。約数の1つが自分自身とペアになるからです。

なぜ上限があるのですか？

試し割りは、そうでなくなるまでは正確で高速です。最悪のケースは平方根に近い2つの素数の積で、ここでの上限は、そのケースでもページの読み込み時間内に答えが返る範囲に設定しています。断られれば何が起きたかがわかりますが、タイムアウトでは何もわかりません。

暗号鍵はこうやって破られるのですか？

いいえ、そこがポイントです。RSAは数百桁の数を素因数分解することの難しさに依拠しています。そうした数に試し割りを行えば、宇宙の寿命より長くかかります。もっと優れた方法は存在しますが、それでも遠く及ばず、だからこそこの仕組みが成り立っているのです。