量子コンピューターでRSA-2048を解くためには？ (2025年5月版)

ARANK

はじめにRSA暗号は、巨大な整数の素因数分解の困難性を安全性の根拠とする公開鍵暗号方式です。特にRSA-2048は、2048ビット長の合成数（10進数で約600桁）を利用しており、現代のスーパーコンピューターをもってしても、既存の素因数分解アルゴリズムでは現実的な時間内での分解は困難です。しかし、もし非常に大規模な量子コンピューターが実現すれば、素因数分解は古典コンピューターと比較して飛躍的に高速化されると予想されています。では、RSA-2048を解読するためには、どの程度の規模の量子コンピューターが必要になるのでしょうか？2019年、GidneyとEkeråは、誤り率0.1%以下の2000万量子ビットを持つ量子コンピューターがあれば、RSA-2048を8時間で解読できるという推定を発表しました。この件に関する日本語の解説は、以下の記事にまとめられています。 に対して、 から までの全ての整数で割り算を試みます。計算量は です。一般数体篩法（GNFS）一般数体篩法（GNFS）は、現在の通常のコンピューター上での大規模整数の素因数分解において最速とされる手法であり、以下の準指数関数の計算量を持っています。GNFSによって、NTTなどの研究チームは、2010年に768ビッ…