RSA768 合成数を素因数分解

RSA768 合成数の素因数分解に成功したらしい。

• Factorization of a 768-bit RSA modulus （ePrint）
• 公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新 ～768ビット合成数を一般数体篩法にて完全分解に成功～
• NTTなど、公開鍵暗号の素因数分解問題で768ビット整数の分解に成功
• 768bit合成数の素因数分解に成功、NTTらが世界記録更新

今回使われた計算手法は「一般数体篩法」と呼ばれるものらしい。 NTT のニュースリリースから一部引用しよう。

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

ちなみに篩では「Opteron 2.2GHz換算で1500年かけたのと同程度の計算量」， 線形代数では「Opteron 2.2GHz換算でおよそ155年の計算量」がかかったそうだ。

参考文献として昔書いた記事を挙げておく。

• 「安全な鍵長の下限」とは

なにせ昔に書いた記事なので， もしかしたらデータが古いかもしれない。 気になる方は NIST や ECRYPT あたりで最新情報を探したらいいだろう。