>>勉強の面倒を毎週見てくれる神サービスがこちら

素因数分解して実際何の役に立つのか?【日常生活の中の数学】

データ分析・統計・数学
この記事は約7分で読めます。

ぶっちゃけ、素因数分解なんかして何の役に立つの?

この記事では、中学生で習う素因数分解が身の回りでいったいどんな役に立っているのかについて、ざっくりと・わかりやすく解説します。

素因数分解は、その困難性を利用して「RSA暗号方式」として活躍しています。

素因数分解とは

素因数分解のおさらいです。わかっているよ、という人は飛ばしてください。

35を素因数分解しなさい。

という問題があります。

これは
「35を素数どうしのかけ算であらわしなさい」
と言っているのと同じことです。

35は「5×7」というかけ算で表すことができて、「5」と「7」はどちらも素数です。

よって答えは「35=5×7」となります。

ネット上の安全を守るセキュリティ

素因数分解が難しいから役に立つ

いきなりですが問題です。

13231を素因数分解しなさい。

…どうですか?なかなか素因数分解ができずに困りませんか。ちなみに答えは「13231=101×131」です。

おそらく皆さんは

13231を11で割って…13で割って…17で割って…

という風に、13231を素数で割っていくという地道な方法で計算したのではないでしょうか。

実は、素因数分解はこういう地道な解き方をするしかないのです。何か公式に当てはめれば素因数分解ができる、とかいう魔法の方法は存在しません。

では次の問題はどうでしょうか??

27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983 を素因数分解せよ。

…200桁の素因数分解です。もはや人間には無理ゲーです。

…でも、コンピューター使えば簡単に求まるんでしょ??

と思う人がいるかもしれませんが、コンピューターでもそう簡単には解けません。最悪10億年という天文学的な時間がかかるのでほぼ不可能です。

このように、100桁とか200桁のレベルの素因数分解となるとほぼ解答不可能な問題になります。

実は、そういった素因数分解の困難性を利用している身近なシステムがこの世の中に存在しています。

それは「暗号」という仕組みです。暗号を使って、ネット上の安全(セキュリティ)を守っているのです。

それでは、暗号のざっくりした仕組みについて、これから説明していきましょう。 

仕組みをざっくり説明

上では、素因数分解が難しいことについて説明してきました。この性質を応用して、暗号を作っていきます。

まず「p」と「q」という2つの素数を持ってきて、この「p」と「q」を暗号を解読するのに使う数字としておきます。もちろんこの「p」「q」がバレると解読されてしまうので、秘密にしておきます。

次に、2つの素数を掛け合わせてしまいましょう(p×q=N)。もしこの「N」という数字が200桁という大きな数であれば、上で述べたように素数「p,q」を素因数分解で求めることはほぼ不可能です。

そのため、「N」をみんなにバラしても、秘密にしてある「p」「q」がバレる心配はほぼありません。なので「N」は皆に公開しちゃいます。(なぜ公開するのかはこれから説明します。)

この公開した「N」は、秘密にしたい情報を暗号化するのに使います(カギをかけるイメージ)。

…あまりイメージがしづらいかもしれませんね。

では、下図を参照しながら具体例で考えてみましょう。

例えば、あなたがWebサービスに登録するときに

Webサービス
Webサービス

あなたの ID は「123456」です。

とIDがメールなどを通じて送られてきたとします。

しかし、このような重要な情報がそのままネット上に流れてしまうと、誰かに盗み見されてしまう危険性があります。なので暗号化の作業を行おうと思います。

公開してある数字「N」の情報を使い、「123456」というID番号を「#15%1*+」のように意味不明な暗号に変換します。

暗号化されたID番号「#15%1*+」を受け取ったあなたは、これを解読します。秘密の素数「p,q」の情報を頼りに計算して、もとのID番号「123456」を求めることができます。

ユーザー
ユーザー

ID番号は「123456」か。

このように、素因数分解の困難性を利用した暗号をRSA暗号と呼んだりします。

RSA暗号方式は安全?

「これでちゃんとID番号は守られているの?」

と思う人もいるかもしれないので、次のような場面を考えてみましょう。

悪い人がID番号を盗み見して、暗号を解読しようとします。そして、解読するための「鍵」を作りました。

しかし、うまく素因数分解できていなかったようです。

なぜなら、ニセモノの「鍵」で暗号解読を試みたけれども失敗してしまったからです。

このように、本人しか知らない「p, q」という素数でないと暗号は解けないようになっているのです。

暗号が解読されてしまうケース

しかし、この暗号は100%安全だとは言えません。

公開されている「N」という整数は素因数分解が難しいとはいえ、100%解けないわけではありません。たまたま素因数分解できてしまった場合は、秘密であるはずの「p, q」の素数が他人にばれてしまいます。(下図参照)

このように、うまく数字を設定しておかないと解読される危険性があります。

もちろん、実際運用されている暗号システムはこれよりも複雑で「素因数分解されたらオワリ」なんてことにはなりません。ここで説明した暗号の仕組みはあくまで簡素的なものなので、もっと複雑な仕組みを知りたいという人は本とか読んでみるといいと思います。

例えばコレ。とても分かりやすく解説されています。↓

今回はここまでです。最後までご覧いただきありがとうございます!

参考

「RSA暗号」フリー百科事典Wikipedia日本語版 (2022年1月19日 最終更新)
https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

「公開鍵暗号方式」情報処理推進機構(2009年9月1日 最終更新)
https://www.ipa.go.jp/security/pki/022.html

この記事は役に立ちましたか?
  • 役に立った 
  • ふつう 
  • 役に立たなかった 

記事への意見・感想はコチラ

タイトルとURLをコピーしました