Shor のアルゴリズム.

大きな整数の素因数分解と離散対数を多項式時間で解く量子アルゴリズムであり、十分な規模の量子計算機上で RSA・Diffie-Hellman・楕円曲線暗号を破る。 サイバーセキュリティの 暗号 カテゴリに属します。

大きな整数の素因数分解と離散対数を多項式時間で解く量子アルゴリズムであり、十分な規模の量子計算機上で RSA・Diffie-Hellman・楕円曲線暗号を破る。

Shor のアルゴリズムは、Peter Shor が 1994 年に発表した量子アルゴリズムで、誤り耐性のある量子計算機上で整数の素因数分解と離散対数問題を多項式時間で解きます。これらの問題は、RSA、Diffie-Hellman、DSA、ECDSA など、現在運用されているほぼすべての公開鍵暗号の安全性の基礎となっています。現状の量子ハードウェアは暗号学的に意味のある鍵長を分解できませんが、信頼できる試算では数千の安定した論理量子ビットがあれば RSA-2048 を破れるとされています。これが NIST の PQC 標準化や、暗号文を先に収集して将来復号する「ハーベスト・ナウ・デクリプト・レイター」型攻撃が問題視される根本的な理由です。

Shor のアルゴリズム に対する防御は通常、上記の定義で述べたとおり、技術的統制と運用上の実践を組み合わせます。

一般的な別名: Shor の因数分解アルゴリズム。