あなたのパスワードは300桁の素数が守る!


要点チェック!
  • 公倍数や公約数を求めるときには、素因数分解を使うと便利です。
  • 素数は、メールやLINEの内容が他人にバレないようにする「暗号化」に利用されています。

あかりー

なになに、ぽんさん?

39は素数かな?

39・・・・3で割れるから素数じゃないよ!

そのとおり!じゃあ49は?

49は素数・・・じゃないに決まってるでしょ!7の2乗だよ!

おお!すばやいね、そうだね笑

じゃあ1001は?

また何かたくらんでる?

・・・う~ん、素数なんじゃない?

残念!
素因数分解すると$$1001=7\times11\times13$$で素数ではありませんでしたー!

あぁぁ…

そういえば、素因数分解って久々に聞いたね・・・


1001の素因数分解1001の素因数分解

じゃあぽんさん、2015は素数?

はは、5で割れるから素数じゃないね。

むう・・・じゃあ2016は?

偶数だから素数じゃないに決まってるじゃないか笑

偶数だから素数じゃない・・・2は素数だよー!

むむむ・・・揚げ足をとってきたね。

なにがむむむだっ!じゃあ2017は素数かな?

うーん・・・。

ちょっと数が大きいな・・・グーグル先生に聞いてみる笑。

ぽんさんでもわからないんだー!

あかり、ムキになってるな笑
2017は素数らしいぞ!

そうなんだ!なんでこんな話でムキになっちゃったんだろ・・・。

素数ってなぜか夢中になるというか、意識してしまうんだよね。俺も数字を見かけたら、こいつは素数かな?って考えてしまうときがある。

えええ・・・

とある理系の工業大学では、素数であるかどうかで学生が一喜一憂するらしいぞ笑

なにそれ笑 変な人たちだね~

素数かどうかなんてとくに意味のないことなのにね!

素数かどうかに意味はない・・・そんなことはないぞ?

へっ、どういうこと?

じゃあ、素因数分解がどう現実で役立っているかという話をしよう。

おお、そんなのあるんだ!

さすがはぽんさん。

でもその前に、ちょっと復習をしよう。

例えば、公倍数や公約数を求めるときに、素因数分解を使うと便利だ。

あかり、48と256の最小公倍数を求めなさい。

えーなんかめんどくさそう…

とりあえず両方かけ合わせてみたらいいんじゃない?

残念!両方かけた数は最小公倍数じゃありません!

ひとまず、48と256を素因数分解してみようか。

素因数分解・・やってみるよ。

素因数分解したら、
$$48=2^{4}\times 3$$
$$256=2^8$$
になったよ。


48,256の素因数分解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時には着くよ!」というメッセージが確認できるというわけさ!


RSARSA暗号化の例

なるほど~なんとなく分かったよ!

でもさ、『11 54 14 44 53 ・・ 34』って数字の列と、91を使って暗号化したよ!っていうのは誰でも知れるんだよね?

そうだね。

じゃあ、91が7と13に 素因数分解されるって分かってたら、誰でも戻せるってこと?

いいところに気づいたね。その通りだよ。

こんな素因数分解、すぐ気づかれるじゃん!これじゃやっぱり情報が駄々漏れだよ!

91は数としては小さいからね。もっと大きい数を使えばいい。

でも、さっき2017は素数ってこと、調べればすぐ分かったでしょ?どれだけ大きい数を使っても、パソコンを使えばあっという間にわかっちゃうよ・・・

いやいや、コンピュータの計算速度は確かにすごいけど、それでも限界はある。

さっき例に出した91は2桁、2017は4桁だけど、コンピュータでも300桁くらいの数を素数か判定したり、素因数分解するには、実は1年くらいかかるといわれている。

いっ、いちねん!

1年間ずっと電源つけっぱなしで計算させるって・・・電気代がもったいないよ!

そこかい笑

まあもっと桁を増やせば、もはや解読は現実的に不可能になるね。

解読されるはるか昔に、あかりはもう家についてるよ!

そうだよね!

この暗号方式は、たとえコンピュータをフル稼働させたとしても、巨大な数の素因数分解が完了するには、非常に時間がかかってしまうことを利用している。

すぐに分かる方法はないの?

まだ見つかっていない。見つかったらこの暗号システムは崩壊するね。簡単に人の情報を盗み見できる世の中になる。

ひええ恐ろしい・・・。分からないほうが世のためになるんだね!

そういうことだね。数学でも「答えが出ないほうがいい」ということもあるってわけだ!

3
もっと楽しい数学のお話あります!