前へ 次へ 
皆さん，素因数分解ってご存じですよね？。昔，中学校の頃習った
て奴です。え！こんなのが暗号の理論なの？と思われるかも知れません。しかし，このくらいなら簡単に因数分解できても，これが200桁の数字になれば簡単には因数分解出来なくなります。
でも，「順番に1,2,3,4,5,6,7……とわり算していけばいいんでしょ。」と思われるかも知れませんが，200桁の数を因数分解しようとすると現在最高速のスーパーコンピュータでも膨大な時間（十億年くらい）がかかってとても実用的ではありません。
素数は2以外は全て奇数ですから「2,3,5,7,9,11,13……」というように2以外は二つずつ飛ばしながらわり算していけば計算の効率は倍になります。しかし，これでも十億年かかる計算が五億年で終わることになるくらいで，たいした差とはなりません。五億年かかって暗号を解読したところで，その頃には解読した暗号の意味なんてとっくに意味のないものになっているでしょう。しかし，200桁の数字は注意深く選ばなくてはなりません。
詳しい説明はしませんが，現在では200桁の数字であっても素数かどうかの判定は比較的短時間に（五分ほど），極めて高い確率で判定可能です。今，ある数字を調べたとき「素数である確率は99.9999999％」である数字があるとします。あなたはこの数字が「そんなに確率が高いなら，たぶん素数じゃないの」と思いますか？，それとも「判定の仕方が悪いだけで本当は素因数分解出来るんじゃないの」と思いますか？。
私は前者だと思います。そこで100％ではないですが，ほぼ素数であろうと考えて間違いがない数字のことを疑似素数と呼ぶことにします。これに対して素因数分解が出来る数字のことを合成数といいます。
そこで，100桁ほどの数字を適当に選んできて疑似素数かどうか判定します。もし，疑似素数でなければ，すぐその次の数を同じように判定します。コンピュータを使えば瞬く間に数万個の数字が判定出来るでしょう。そのようにして選び出した疑似素数を二つ選びます。
もちろん，この二つの数字は素数である確率が極めて高いだけで，素数であるという確証があるわけではないので，この二つの数字はいくつもある素数判定法を用いて繰り返し判定をしなくてはなりません。
「素数でない」という判定が出れば，素因数分解が出来るはずですが始めに述べたように200桁の数字の素因数分解は十億年という時間がかかるので，ほぼ安全です。
前へ 次へ