メインメニューをとばして、このページの本文エリアへ

漫画で解説

素数の不思議の巻

1と自分の数以外では割り切れない 暗号技術に大きな役割

[PR]

2016年1月に米国セントラルミズーリ大学の研究者 カーティス・クーパー教授が過去最大の素数を発見しました。 古代ギリシャの数学者ユークリッドは、 素数とは1と自分の数以外では割り切れない自然数で、 無限にあると示していましたが…。 一体、素数はどのようにして見つけるのでしょうか。
素数を見つけるには「エラトステネフのふるい」という方法が有名です。 例えば、100までの素数を見つけたい場合、 100の平方根である10までの素数、つまり、2・3・5・7の倍数を消していきます。 2の倍数は4・6・8・・・、3の倍数は6・9・12・15・・・、 5の倍数は10・15・20・25・・・、7の倍数は14・21・28・35・・・。 このようにして、出てきた数をそれぞれ消していくと残った数が100までの素数となります。 しかし、それでも大きな数の素数を見つけることは大変そう…。 そこでクーパー教授はメルセンヌ数「2のn乗-1」という数式から素数を探しています。 今回、発見した素数は2233万8618桁で、 コンピューター800台が使われました。 特に素数は暗号技術に使われていて重要なのです。
素数の暗号技術とは、RSA暗号といって、 大きな数が何の素数の積か見つけるのに 時間のかかることを利用した暗号です。 二つの素数から積を求めるのが簡単であっても、 素数の積から2つの素数に分解することは困難なことを利用した仕組みなんです。 例えば、ネットショッピングなどに使われています。 AさんからBさんへ秘密の数字を送りたいとします。 BさんはAさんに素数の積3208411を送ります。 Aさんはこの積を使いAさんの秘密の数字1234を暗号化しBさんに送ります。 Aさんから暗号化された秘密の数字を受け取ったBさんは 自分の持つ素数の積を分解させた1123・2857の2つの素数を使い、 Aさんの秘密の数字1234を復元させるのです。 暗号が途中で第三者に漏れても第三者は その数の素数を探し当てなくてはならず復元は難しいのです。 暗号を解読するのが難しいからこそ、クレジットカード番号も安全なのです。
このRSA暗号は3人の研究者の頭文字、 リベスト(R)・シャミア(S)・アドルマン(A)からとったそうです。 RSA暗号は効率的な素因数分解の算出方法が 発見されれば安全性は低下するでしょう。 しかし、その方法は2000年もの間発見されていない上に、 RSAに対し素因数分解を解く以外の方法で有力な攻撃方法はありません。 つまり、素数が大きければ大きいほど暗号の安全性は増すのです。 素因数分解の宿題に苦労している中学生のののか。 素数のことは理解できたようですが、宿題の難しさは変わらないようです…。

おすすめ記事

広告
毎日新聞のアカウント
ピックアップ
話題の記事

アクセスランキング

毎時01分更新

  1. 独で歩行者に車突っ込み乳児含む5人死亡 飲酒運転の容疑者逮捕

  2. 「山を一つ動かしたかな」桜を見る会問題追及、田村智子参院議員に聞く

  3. #排除する政治~学術会議問題を考える 「まるでモラハラのよう」 矛盾だらけの「改革」論議 名大・隠岐さや香教授

  4. 学術会議現役会員「世界から笑われる」 政府、非政府組織化を提案

  5. 社会から「消された存在」だった 18年軟禁された女性、自立探る今

編集部のオススメ記事

のマークについて

今週のおすすめ
毎日新聞社は、東京2020大会のオフィシャルパートナーです