NTTは1月7日、スイス連邦工科大学ローザンヌ校(EPFL)、独ボン大学、フランス国立情報学自動制御研究所(INRIA)、オランダ国立情報工学・数学研究所(CWI)との共同研究により、素因数分解問題において、従来の世界記録である663ビット(10進200桁)を上回る、768ビット(10進 232桁)の合成数に対して、一般数体篩法による素因数分解を達成したことを発表した。

現在、公開鍵暗号として用いられているRSA暗号は素因数分解の難しさを安全性の根拠としているため、素因数分解可能なビット数の検証はRSA暗号の安全性、強度の有効性を予測する上で重要なものとなっている。

NTTらは今回、700ビットを超す素因数分解を達成したが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成される可能性があることを示唆することとなり、より高い強度かつ効率的な暗号技術を利用する必要性が高まることを意味する。

研究内容は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法を用いて実施された。同法は、多項式選択、篩(ふるい)、filtering、線形代数、平方根の5つのステップからなり、このうち、篩と線形代数が最も計算量を要するステップとなっている。

各ステップにおいて、選択すべきパラメータは多数あり、このパラメータの選択によって計算量が大きく変化するが、その有効な選択方法については多くの場合においてまだ解明されていない。今回の共同研究では、このパラメータを適切に選択することで、高速に計算することに成功したという。

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

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

その結果、最終ステップとなる平方根(代数的数の平方根の計算及び最小公約数の計算)では、EPFLに設置された計算機を用いることで、数時間で以下の解を得たという。

なお、同結果を受けてNTTでは、NTT研究所にて暗号技術全般の安全性を継続的に評価していくとするほか、次世代暗号として楕円曲線上の演算規則を利用した新しい公開鍵暗号方式「楕円曲線暗号」の普及にも努めていくとしている。