6=2×3。15=3×5。2021=〇×△だ！ちょっとディープな素因数分解の世界

普段、私たちが見ているこの世界。
ほんの少しだけ「数学」を知ってみると、意外な奥行きが見えてくるかもしれません。

今回は、ちょっとディープな素因数分解の世界に覗いてみましょう！

「素因数分解」って、何だっけ？

「素数」や「素因数分解」という言葉が、数学に馴染みがなくても、「聞いたことある！」「小中学校で習った！」という人が多いのではないでしょうか。

では、この「素数」と「素因数分解」を、少し復習してみましょう。

「素数」というのは「1より大きい整数で、1と自分自身以外に正の約数を持たない数」のことです。
※1より大きい整数とは、「2、3、4、5、6…」のことです。

こんな風に書くと難しく見えますが、具体例を見てみるとピンと来るはずです。

例えば、2、3、5、7はどれも素数です。どれも「1と自分自身以外」では割り切ることができません。

一方、6は2と3で割り切れるので素数ではありません。「1と自分自身以外」である「2と3」で割り切ることができます。

また、「素因数分解」は、「正の整数を素数の積で表すこと」です。

「2021」を素因数分解すると…？

「素因数分解」について、具体例を見てみましょう。

例えば、

\[
6=2\times3\\
\]

\[
12=2\times2\times3\\
\]

\[
15=3\times5\\
\]

といった具合に「素数の積」で表現することが素因数分解です。

では、今年の西暦である「2021」を素因数分解してみましょう。一見、なんとなく素数っぽいですね。

しかし、実は素数ではなく…

\[
2021=43\times47\\
\]

と素因数分解することができます。

このように、少し大きな数の場合、6や12や15のようにパッと見で素因数分解することは、なかなか難しいです。しかも2021の場合は、割り切る素数（43と47）が、若干大きいことも厄介です。

実は超難しい「素因数分解」

では次に、もっと大きな数を素因数分解してみましょう。

\[
4294967297
\]

42兆を超える、かなり大きな数です。

これを素因数分解すると…

\[
4294967297=641\times6700417\\
\]

となります。ここまで大きな数だと、さすがに手計算では出来なさそうですね…。

実は、「大きな整数の素因数分解はかなり難しい」というのは、コンピュータにとっても同じことなのです。

もちろん、今のコンピュータは、4294967297くらいの数であれば、一瞬で素因数分解することができます。しかし、もっと桁数を増やしてしまうと事情は変わります。

このことについて、数学者黒川信重の著作である「リーマン予想の今,そして解決への展望」には、以下のように書かれています。

“Nが200ケタ程度の2つの素数の積であることも知っていたとしても、N=pqとなるpとqを求めるためには[中略]、現在の技術では、数千年程度の時間がかかる”

これだけ、コンピュータが発達している現代であっても、素因数分解に数千年もかかるとは驚きです。

ちなみに、先ほどの例で挙げた4294967297という数は、17世紀の大数学者フェルマーが「素数だ」と思っていた数です。この数が素数でないことが確認され、素因数分解されたのは、なんと約100年後のこと。

それほどまでに、素因数分解は難しいのです。

現代の生活に欠かせない「素因数分解」

「素因数分解が難しくても、私には関係ないし…」と思った方もいるかもしれません。しかし、素因数分解は、現代の私たちの生活に密接に関わっています。

それは、情報セキュリティです。

例えば、オンラインで買い物をする際に、クレジットカードの情報を送信します。その際、第三者から情報を盗まれることなどがないように「暗号化」という技術を使っています。

「RSA暗号」という暗号では、「素因数分解の難しさ」が重要なカギになっています。「大きな整数の素因数分解はかなり難しく、現代の技術では膨大な時間がかかること」が、RSA暗号の安全性を支えているのです。

子どもの頃に学ぶ素因数分解ですが、現代のコンピュータ技術にまで関わっており、私たちの生活に必要不可欠なものとなっています。