« 出かけました(2016年6月) | トップページ | 「球の表面のザラザラさ」の科学 »

2016年6月19日 (日)

安全素数

 今日は、年(下2桁)月日「160619」と月日「619」がともに素数の日。さらに言えば、双子素数(160619,160621)、三つ子素数(613,617,619)になっていたりする。これだけ揃っていたら、今日は久しぶりに素数のネタにするべきだろう。

 ということで、今回は今日の日付にまつわる素数の話にしようと思ったが、これまでも結構素数のネタは書いてきたので、新たな話題が見つかるかどうか半信半疑のまま少し調べてみたら、ブログで取り上げたことがない話が見つかった。

 「安全素数safe prime)」という数について聞いたことがあるだろうか。正直なところ、私は今回調べてみて初めて知ったのだが、「p」と「2p+1」がともに素数である時に、大きい「2p+1」の方の数を安全素数と呼ぶそうだ。

 例えば、

p=80309

は素数だが、この時

2p+1=160619

も素数なので、「160619」は、この安全素数になっている。

 また、「p」と「2p+1」がともに素数である時の小さい「p」の方は「ソフィー・ジェルマン素数Sophie Germain prime)」と呼ばれている。

 実は「160619」は、2倍して1を加えた「321239」も素数のため、ソフィー・ジェルマン素数でもある。

 さらに、この3つの素数の列「80309, 160619, 321239」は「第一種カニンガム鎖(Cunningham chain)」と呼ばれているものにもなっている。

 ところで、「安全」という言葉は、実際に暗号理論に由来しているそうだ。

 もう少し詳しく調べてみると、インターネットでよく利用されている「公開鍵暗号」の仕組みが関係しているらしい。例えば、この仕組みを利用している代表的な電子署名方式の中に「素体の乗法群上の離散対数問題」の解決困難性を利用した公開鍵暗号で機密性を保持しているものが多い、というようなことがWikipediaなどに書かれている。

 ただ、与えられた数字に対して、「それから1をひいた数」が(2以外の)小さな素数で割り切れてしまうものだと、離散対数問題と呼ばれる問題を比較的容易に解決できる方法(Pohlig–Hellman algorithm)があるらしく、そういった数字を暗号として使うことは非常に危険となる。

 一方、「p」を比較的大きな素数でかつ「2p+1」も素数の時、この安全素数「2p+1」を使えば、1を引いた「2p」は2以外では「比較的大きな素数 p」でしか割り切れないため、離散対数問題と呼ばれる問題を解くのは非常に困難らしい。

 要するに、大きな「安全素数」を使えば第三者が問題を解決して機密を得ることが非常に困難(実質的に無理)なため署名の機密性が保持されるから「安全」ということのようだ。

 ということで、今回は「安全素数」の話題になった。なんだか、今日の年月日の数字がとっても役にたつ素数と関係している、というのはなんとなく気分がいい。また素数の日に色々ネタが見つかれば、ブログで紹介しようと思う。

--------

Copyright (c) 2016 ANADA, Koichi. All Rights Reserved.

« 出かけました(2016年6月) | トップページ | 「球の表面のザラザラさ」の科学 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« 出かけました(2016年6月) | トップページ | 「球の表面のザラザラさ」の科学 »