科学好き者の日々

SSL通信は公開鍵暗号を使っているとのことです。

公開鍵暗号ではRSA方式が有名ですね。

以下Wikipediaよりの引用です。

この方式の安全性は素因数分解の困難性に基づいている。詳しくは、RSA暗号を参照。

素数 p, q が与えられたとき、その積 n = pq を計算することは容易である。しかし逆に、2つの素数の積であるような自然数 n が与えられたとき、n = pq と素因数分解することは難しい。鍵の大きさ（すなわちp, q のビット数）が十分に大きければ、素因数分解にはとてつもない時間が掛かる。

暗号化には n を、復号には p と q を必要とするようなうまい仕組みを作っておく。そして、n を公開鍵として公開する。傍受者は n から p,q を割り出そうとするが、これは時間が掛かりすぎて現実的でない。

もちろん、根気強く分解を試みればいつかは復号に成功するわけである。しかし、一般市民の個人的な通信程度であれば、解読に数年を要する規模の暗号化を施しておけば、それ以上の手間暇を掛けて解読しようとする者はまずいない。これは、事実上秘密が守られていると言える。

軍事用暗号の場合、専用のコンピュータで専門のプログラムを走らせても解読には数億年～数兆年を要するように設計されている。これは、事実上解読不可能と言ってよい。

引用終わり

素数を求めるのは、コンピュータープログラミングを始めた人が最初にするプログラムのような気がします。（Hello, worldと表示させるのは終わったとして）

２つの自然数である変数（n,m）を用意して、ｎを２から始まるｍで割って割り切れなければ（あまりがあれば）ｍを＋１してまた割る。ｍをn-1までにしても割り切れなければ素数とし、途中で割り切れればｎは素数ではないとしてｎを＋１して次の数を調べる。
という単純なアルゴリズムでプログラムをつくることができます。（もうちょっとエレガントな方法はありますがね）

上記のように素数を求めるのに短時間でできる方法はありません。ただひたすら割り算をして割り切れるかを確認していくわけで、コンピューターでも素数の桁数が多くなると指数関数的に時間がかかるわけですね。

初めて1000くらいまでの素数を求められたときはちょっと感激でした。