- 公倍数や公約数を求めるときには、素因数分解を使うと便利です。
- 素数は、メールやLINEの内容が他人にバレないようにする「暗号化」に利用されています。
あかりー
なになに、ぽんさん?
39は素数かな?
39・・・・3で割れるから素数じゃないよ!
そのとおり!じゃあ49は?
49は素数・・・じゃないに決まってるでしょ!7の2乗だよ!
おお!すばやいね、そうだね笑
じゃあ1001は?
また何かたくらんでる?
・・・う~ん、素数なんじゃない?
残念!
素因数分解すると$$1001=7\times11\times13$$で素数ではありませんでしたー!
あぁぁ…
そういえば、素因数分解って久々に聞いたね・・・
じゃあぽんさん、2015は素数?
はは、5で割れるから素数じゃないね。
むう・・・じゃあ2016は?
偶数だから素数じゃないに決まってるじゃないか笑
偶数だから素数じゃない・・・2は素数だよー!
むむむ・・・揚げ足をとってきたね。
なにがむむむだっ!じゃあ2017は素数かな?
うーん・・・。
ちょっと数が大きいな・・・グーグル先生に聞いてみる笑。
ぽんさんでもわからないんだー!
あかり、ムキになってるな笑
2017は素数らしいぞ!
そうなんだ!なんでこんな話でムキになっちゃったんだろ・・・。
素数ってなぜか夢中になるというか、意識してしまうんだよね。俺も数字を見かけたら、こいつは素数かな?って考えてしまうときがある。
えええ・・・
とある理系の工業大学では、素数であるかどうかで学生が一喜一憂するらしいぞ笑
なにそれ笑 変な人たちだね~
素数かどうかなんてとくに意味のないことなのにね!
素数かどうかに意味はない・・・そんなことはないぞ?
へっ、どういうこと?
じゃあ、素因数分解がどう現実で役立っているかという話をしよう。
おお、そんなのあるんだ!
さすがはぽんさん。
でもその前に、ちょっと復習をしよう。
例えば、公倍数や公約数を求めるときに、素因数分解を使うと便利だ。
あかり、48と256の最小公倍数を求めなさい。
えーなんかめんどくさそう…
とりあえず両方かけ合わせてみたらいいんじゃない?
残念!両方かけた数は最小公倍数じゃありません!
ひとまず、48と256を素因数分解してみようか。
素因数分解・・やってみるよ。
素因数分解したら、
$$48=2^{4}\times 3$$
$$256=2^8$$
になったよ。
そうだね。
最小公倍数ということは、それぞれの素因数分解で出てきた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時には着くよ!」というメッセージが確認できるというわけさ!
なるほど~なんとなく分かったよ!
でもさ、『11 54 14 44 53 ・・ 34』って数字の列と、91を使って暗号化したよ!っていうのは誰でも知れるんだよね?
そうだね。
じゃあ、91が7と13に 素因数分解されるって分かってたら、誰でも戻せるってこと?
いいところに気づいたね。その通りだよ。
こんな素因数分解、すぐ気づかれるじゃん!これじゃやっぱり情報が駄々漏れだよ!
91は数としては小さいからね。もっと大きい数を使えばいい。
でも、さっき2017は素数ってこと、調べればすぐ分かったでしょ?どれだけ大きい数を使っても、パソコンを使えばあっという間にわかっちゃうよ・・・
いやいや、コンピュータの計算速度は確かにすごいけど、それでも限界はある。
さっき例に出した91は2桁、2017は4桁だけど、コンピュータでも300桁くらいの数を素数か判定したり、素因数分解するには、実は1年くらいかかるといわれている。
いっ、いちねん!
1年間ずっと電源つけっぱなしで計算させるって・・・電気代がもったいないよ!
そこかい笑
まあもっと桁を増やせば、もはや解読は現実的に不可能になるね。
解読されるはるか昔に、あかりはもう家についてるよ!
そうだよね!
この暗号方式は、たとえコンピュータをフル稼働させたとしても、巨大な数の素因数分解が完了するには、非常に時間がかかってしまうことを利用している。
すぐに分かる方法はないの?
まだ見つかっていない。見つかったらこの暗号システムは崩壊するね。簡単に人の情報を盗み見できる世の中になる。
ひええ恐ろしい・・・。分からないほうが世のためになるんだね!
そういうことだね。数学でも「答えが出ないほうがいい」ということもあるってわけだ!