セキュリティ
上級
Shor's Algorithm (1994年)（ショアズアルゴリズム）
Shor's Algorithm は1994年Peter Shor (米国Bell Labs・MIT 後Caltech・1985-1994年Bell Labs 研究員) 発表の量子アルゴリズムでRSA 暗号 (2048-bit) の基盤である大整数因数分解を量子コンピュータで多項式時間 (O((log N)^3)) で解く・古典コンピュータでは指数時間 (O(exp(c·(log N)^{1/3}))) のため現代RSA/ECC 暗号が将来の量子コンピュータに破られる「Q-Day」(暗号崩壊日) の理論的起点。
0 回閲覧
0 いいね
2026/5/14 更新
関連タグ
shor-algorithm
1994
peter-shor
bell-labs
integer-factorization
rsa-2048-break
quantum-cryptanalysis
focs-1994
quantum-history
q-day
quantum-apocalypse
Shor's Algorithm (1994年)
概要
Shor's Algorithm は1994年Peter Shor (Bell Labs) 発表の量子アルゴリズムでRSA 暗号の基盤である大整数因数分解を量子コンピュータで多項式時間で解く・古典コンピュータでは指数時間のため現代RSA/ECC 暗号が将来の量子コンピュータに破られる「Q-Day」の理論的起点。
主な特徴・仕組み
- 発表: 1994年4月20日Peter Shor「Algorithms for Quantum Computation: Discrete Logarithms and Factoring」FOCS 1994
- 計算量: O((log N)^3) 多項式時間 (古典GNFS は O(exp(c·(log N)^{1/3})) 指数時間)
- RSA-2048 破壊: 古典PC で 10^{34}年 → 量子コンピュータで数時間-数日
- 必要量子ビット数: 4,000+ qubit (RSA-2048) ・現代Google Willow 105 qubit・IBM Condor 1,121 qubit
- Q-Day 予測: 2030年代-2040年代到達
- Peter Shor 経歴: 1959年-・MIT 卒・Bell Labs 1985-1994年→MIT 教授 2003年-現代・1999年Nevanlinna Prize・2017年Dirac Medal
- 後継: Post-Quantum Cryptography (PQC) ・2024年8月NIST FIPS 203/204/205 標準化
まとめ
- 1994年Peter Shor (Bell Labs) 発表
- RSA-2048 因数分解を多項式時間で
- 古典コンピュータでは指数時間
- 「Q-Day」(暗号崩壊日) の起点
- Post-Quantum Cryptography 標準化動機