公開鍵暗号の安全性の根拠である「素因数分解問題」

cnetを見ていたら、
NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか
http://japan.cnet.com/news/sec/story/0,2000056024,20406400,00.htm
という記事を見つけた。

この記事を読んで知ったことがたくさんあり、
忘れないようにブログに残しておきたい。

　NTTは1月8日、グループのNTT情報流通プラットフォーム研究所（NTT研究所）が海外の研究機関と共同で、公開鍵暗号の安全性の根拠となる「素因数分解問題」で世界記録を更新したことを発表した。

　これまでの世界記録は663ビット、10進200ケタだが、新しい世界記録は768ビット、10進232ケタで100ビット以上上回っている。独ボン大学、仏の国立情報学自動制御研究所（INRIA）、オランダの国立情報工学・数学研究所（CWI）と共同で研究した。・・・後略

大きな素数が暗号化にとって大切なであり、素因数分解問題とは、合成数を素数の積に分解するというものである。RSA暗号に使われるような、大きな2つの素数の積から構成される合成数の素因数分解法は「数体篩（ふるい）法」が用いられていて、現在、RSA暗号に使われる合成数には「一般数体篩法」と呼ばれるやり方が高速とされている。
この「一般数体篩法」を活用して「素因数分解問題」で世界記録更新したそうです。

一般数体篩法は、

1. 多項式選択
2. 篩（ふるい）
3. filtering
4. 線形代数
5. 平方根

という5つのステップから構成されることがわかった。

1.多項式選択
　このステップは残りの計算量を決める重要なステップ。

2.篩（ふるい）処理
　このステップは全体の計算量の大半を占めますが、比較的容易に分散計算可能であることから多数の参加組織により並列に計算を行う。

3.filtering
　このステップを実行することにより、この次の線形代数ステップを桁違いに高速に実行することができるようになる。

4.線形代数（連立方程式の解法）
　このステップは理論的には最も計算量を要するステップのひとつであり、分散計算が困難。

5.平方根（代数的数の平方根の計算及び最小公約数の計算）
　このステップは数学的には高度な理論を用いますが計算量はさほど要しない。

次世代暗号として、楕円曲線上の演算規則を利用した「楕円曲線暗号」があるそうです。

参考サイト
News Release 100108a
公開鍵暗号の安全性の根拠である「素因数分解問題」で
世界記録を更新
http://www.ntt.co.jp/news/news10/1001/100108a.html