RSA768 合成数を素因数分解

no extension

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

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

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

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

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

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