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

漫画で解説

素数の不思議の巻

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月下旬」IOC委員 新型コロナ感染拡大で

  2. 海からイノシシ、窒息死させて返り討ち 長崎の50代男性に警察官もビックリ

  3. 新型コロナの影響で旅館が経営破綻 愛知の「冨士見荘」が破産申請 キャンセル相次ぐ

  4. 新型コロナ対応「先手先手だと思いますよ。しっかりやっている」 菅官房長官会見詳報

  5. 強い感染力、基礎疾患で重症化…新型コロナの「非常にやっかい」な特性 政府の課題は

編集部のオススメ記事

のマークについて

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