特殊数体篩法の世界記録更新

特殊数体篩法による素因数分解記録が更新されました。1017 ビット合成数を、日本のＮＴＴ・ドイツのボン大学・スイスのスイス連邦工科大学ローザンヌ校の連合チームが分解したそうです。これまでの記録は 911 ビットだったので、相当な世界記録の更新となっています (このレベルで 100 ビットも記録が伸びるのは大変なことなのです)。大ニュースですね！でも切りの良い 1024 ビット合成数をターゲットにしなかったのはどうしてかなぁ？

この手のニュースが報道されると、決まって 1024 ビット鍵の RSA 暗号がいつ破られるか？（つまりいつ 1024 ビット合成数が分解できるか？）という話になるわけです。まず誤解してはいけないのは、今回使用された特殊数体篩法という素因数分解法は、そのままでは RSA 暗号で使用する合成数には適用できないという点です。特殊数体篩法は、素因数分解法として最も強力な方法である一般数体篩法の仲間ではありますが、特殊というだけあって、適用できる合成数にも大きな制約があるわけです。つまり、RSA 暗号の 1024 ビット鍵がただちに分解されるわけではありません。

ただ、同じ数体篩法ですので、新しく得られる知見もあるわけです。経験的に、特殊数体篩法の世界記録は一般数体篩法の世界記録の約１.５倍になることが知られています。この換算でいくと、今回の記録は約 678 ビットの RSA 暗号の鍵を分解したことに相当しています（プレスリリースでも「約 700 ビット」と換算されています）。ちなみに一般数体篩法の世界記録は 663 ビットです。したがって、今回の素因数分解により、一般数体篩法の記録更新も期待できるわけです。しかしこの観点でも RSA 暗号の 1024 ビット鍵がただちに分解されるわけではありません。

もう一つ注目したいのは、数体篩法の線型代数ステップは 1000 ビット越えても処理可能だということです。ここからはかなり細かい話になるのですが、数体篩法は多項式選択・篩・フィルタリング・線型代数・平方根計算という５つの内部処理から構成されています。特殊数体篩法は分解する合成数を特別な型に限定することによって、多項式選択ステップを省略するのに対し、それ以外の処理は特殊数体篩法でも一般数体篩法でもほぼ共通です。今回の特殊数体篩法が 1017 ビット合成数を分解したということは、このサイズに対する線型代数ステップも処理できたということなので、一般数体篩法によって 1024 ビット合成数を分解する際に、線型代数ステップは問題にならないことがわかります。多項式選択ステップと篩ステップがヤマですね。

今回の記録更新により、次のターゲットは一般数体篩法による 768 ビット合成数の分解に移ったと見るべきでしょう。1024 ビットの分解はまだまだ先ですが、着実に近づいているという実感も持ちます。