素因数分解はネットの安全を守っている！？

要点チェック！
公倍数や公約数を求めるときには、素因数分解を使うと便利です。
素数は、メールやLINEの内容が他人にバレないようにする「暗号化」に利用されています。
あかりー
なになに、ぽんさん？
39は素数かな？
39････3で割れるから素数じゃないよ！
そのとおり！じゃあ49は？
49は素数・・・じゃないに決まってるでしょ！7の2乗だよ！
おお！すばやいね、そうだね笑
じゃあ1001は？
また何かたくらんでる？
･･･う～ん、素数なんじゃない？
残念！
素因数分解すると$$1001=7\times11\times13$$で素数ではありませんでしたー！
あぁぁ…
そういえば、素因数分解って久々に聞いたね･･･

1001の素因数分解
じゃあぽんさん、2015は素数？
はは、5で割れるから素数じゃないね。
むう･･･じゃあ2016は？
偶数だから素数じゃないに決まってるじゃないか笑
偶数だから素数じゃない･･･2は素数だよー！
むむむ･･･揚げ足をとってきたね。
なにがむむむだっ！じゃあ2017は素数かな？
うーん･･･。
ちょっと数が大きいな･･･グーグル先生に聞いてみる笑。
ぽんさんでもわからないんだー！
あかり、ムキになってるな笑
2017は素数らしいぞ！
そうなんだ！なんでこんな話でムキになっちゃったんだろ･･･。
素数ってなぜか夢中になるというか、意識してしまうんだよね。俺も数字を見かけたら、こいつは素数かな？って考えてしまうときがある。
えええ･･･
とある理系の工業大学では、素数であるかどうかで学生が一喜一憂するらしいぞ笑
なにそれ笑 変な人たちだね～
素数かどうかなんてとくに意味のないことなのにね！
素数かどうかに意味はない･･･そんなことはないぞ？
へっ、どういうこと？
じゃあ、素因数分解がどう現実で役立っているかという話をしよう。
おお、そんなのあるんだ！
さすがはぽんさん。
でもその前に、ちょっと復習をしよう。
例えば、公倍数や公約数を求めるときに、素因数分解を使うと便利だ。
あかり、48と256の最小公倍数を求めなさい。
えーなんかめんどくさそう…
とりあえず両方かけ合わせてみたらいいんじゃない？
残念！両方かけた数は最小公倍数じゃありません！
ひとまず、48と256を素因数分解してみようか。
素因数分解･･やってみるよ。
素因数分解したら、
$$48=2^{4}\times 3$$
$$256=2^8$$
になったよ。

48,256の素因数分解
そうだね。
最小公倍数ということは、それぞれの素因数分解で出てきた2や3が「最低限」含まれていればいい。
48には2が4個、3が1個入っているし、256には、2が8個入っている。
つまり･･2が8個、3が1個入っているのが48と256の最小公倍数だってこと？
そうそう！
ということで、$$2^{8} \times 3 = 768$$が48と256の最小公倍数だ。
なるほど！

素因数分解と暗号
そういえばあかり、学校の帰りが遅いときって、何時に学校を出る？
え？
ちょっとテニスが長引いたときとかで、それでも6時半には学校を出るな～
そういう場合、家に連絡したりする？
するよ！お母さんに、「今から帰る～」ってメールしたりね！
家に何時に着くか知らせないと心配だろうしね！
じゃあもし、そのメールのやり取りが全世界に公開されているとしたら？
えっ…
あまりいい気はしないなぁ･･･
その情報を知った誰かが、あかりに付きまとうかもしれないしね。
うわっ、きもちわるっ！
でも、もちろんその情報は、送り手のあかりとその受け手のお母さん以外知ることはない。なぜなら、暗号化されているからだ。
その「暗号化」の一部に、素数と素因数分解が使われているという話をしよう。いわゆるRSA暗号というものだ。
RSA暗号･･･
あかりが「今から帰る～！7時には着くよ！」というメールをお母さんに送るとしよう。
まずこの文字列を数字へと変換する。これは容易に可能だ。
例えば、「あ」は1、「い」は2、…とかね！
そして、ある素数PとQとの積PQを使ってこの数字の列を暗号化する。
数を使って暗号化する･･･難しい話になってきたね。
PQをつかってどう暗号化するのかは結構難しい話だから省略するよ。
それで暗号化されたメッセージが受け手に到達する。
情報の受け手は、暗号化に使われた数PQが、PとQに素因数分解できることを知っている。
そして、その2つの素数P,Qを使って、暗号化されたメッセージを元に戻せるんだ。これがRSA暗号。
んー？ちょっとPだのQだのPQだの、わかりにくいよ！
じゃあ、例えば、P=7,Q=13としよう。するとPQ=91となる。
『今から帰る～！7時には着くよ！』というメッセージを数字の列に変換して、それを91という数を使って暗号化する。
そして暗号文『11 54 14 44 53 ･･　34』という数字の列ができたとしよう。91を使って暗号化したというのは公開されていて、この数字の列も誰でも見れる。
メッセージの受け手側は、91が7と13に素因数分解できることを知っている。この暗号文は7と13という2つの数を使うことにより、元に戻せるんだ。
暗号になっている数字の列が、7と13を使えば元のメッセージに直せるってこと？
そうそう！これで受け手は「今から帰る～！7時には着くよ！」というメッセージが確認できるというわけさ！

RSA暗号化の例
なるほど～なんとなく分かったよ！
でもさ、『11 54 14 44 53 ･･　34』って数字の列と、91を使って暗号化したよ！っていうのは誰でも知れるんだよね？
そうだね。
じゃあ、91が7と13に　素因数分解されるって分かってたら、誰でも戻せるってこと？
いいところに気づいたね。その通りだよ。
こんな素因数分解、すぐ気づかれるじゃん！これじゃやっぱり情報が駄々漏れだよ！
91は数としては小さいからね。もっと大きい数を使えばいい。
でも、さっき2017は素数ってこと、調べればすぐ分かったでしょ？どれだけ大きい数を使っても、パソコンを使えばあっという間にわかっちゃうよ･･･
いやいや、コンピュータの計算速度は確かにすごいけど、それでも限界はある。
さっき例に出した91は2桁、2017は4桁だけど、コンピュータでも300桁くらいの数を素数か判定したり、素因数分解するには、実は1年くらいかかるといわれている。
いっ、いちねん！
1年間ずっと電源つけっぱなしで計算させるって・・・電気代がもったいないよ！
そこかい笑
まあもっと桁を増やせば、もはや解読は現実的に不可能になるね。
解読されるはるか昔に、あかりはもう家についてるよ！
そうだよね！
この暗号方式は、たとえコンピュータをフル稼働させたとしても、巨大な数の素因数分解が完了するには、非常に時間がかかってしまうことを利用している。
すぐに分かる方法はないの？
まだ見つかっていない。見つかったらこの暗号システムは崩壊するね。簡単に人の情報を盗み見できる世の中になる。
ひええ恐ろしい･･･。分からないほうが世のためになるんだね！
そういうことだね。数学でも「答えが出ないほうがいい」ということもあるってわけだ！