NTTは、スイス連邦工科大学ローザンヌ校(以下、EPFL)、ドイツのボン大学、フランスの国立情報学自動制御研究所(以下、INRIA)、オランダの国立情報工学・数学研究所(以下、CWI)との共同研究により、わずかなビット数でも桁違いの計算量が必要となる素因数分解問題において、これまでの世界記録(663ビット、10進200桁)を大きく上回り、768ビット(10進 232桁)の合成数に対して一般数体篩法による素因数分解を達成し、世界記録を更新した。

研究の内容

今回の素因数分解は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法により実現した。一般数体篩法は、多項式選択、篩（ふるい）、filtering、線形代数、平方根の５つのステップからなっている。このうち、篩と線形代数が最も計算量を要するステップである。各ステップにおいて、選択すべきパラメータが多数あり、このパラメータの選択によって計算量が大きく変化するが、その有効な選択方法については、まだ解明されていない。今回の共同研究では、このパラメータを適切に選択することにより、高速に計算することに成功した。以下、今回の分解におけるそれぞれのステップの概要を示す。

①多項式選択

今回は、2005年夏、ボン大学においてOpteron 2.2GHzをおよそ20年かけたのと同程度の計算量で探索して得られた多項式を選択。その後、2007年はじめにEPFLでさらによい多項式の探索を試みたが、Opteron 2.2GHz換算で20年かけたのと同程度の計算量を費やしても見つからなかった。

②篩（ふるい）処理

このステップは全体の計算量の大半を占めるが、比較的容易に分散計算可能であることから多数の参加組織により並列に計算を行った。今回の計算では、利用可能計算機のメモリ容量に応じいくつかのパラメータを準備。2007年夏から開始し2009年４月に終了した。篩処理は主にNTT研究所、EPFL、ボン大、INRIA、CWIの多種多様のPCやクラスタを用いた。全体ではおよそOpteron 2.2GHz換算で1500年かけたのと同程度の計算量を要した。

③filtering

EPFLにある10TBのハードディスクを備えた8コア計算機とクラスタを利用した。様々なパラメータで何度かやり直したことにより、Core2 2.66GHz換算で6カ月以下の計算量であった。

④線形代数（連立方程式の解法）

分散計算が困難なこのステップでは、今回、少数のクラスタを利用し、またそれぞれのクラスタの速度や空き時間が異なっていても効率的に計算できる手法を開発・利用した。NTT研究所及びEPFLのクラスタ、またINRIAはフランスにあるALADDIN-G5Kを効率的に用い、filteringで生成された疎行列からなる連立方程式を解いた。Opteron 2.2GHz換算でおよそ155年の計算量を要した結果、分解に利用可能な解が得られた。

⑤平方根（代数的数の平方根の計算及び最小公約数の計算）

このステップは数学的には高度な理論を用いるが、計算量はさほど要しない。EPFLに設置された計算機を用い、数時間で700ビットを大幅に超える素因数分界を達成した。

今後の展望

NTT研究所は暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として楕円曲線上の演算規則を利用した新しい公開鍵暗号方式「楕円曲線暗号」の普及にも努めていくほか、今後も、暗号理論から社会的影響まで幅広い領域におけるセキュリティ研究を推進し、ネットワーク社会の安心・安全を追求していくとしている。