概要\n\nShor algorithm(ショア アルゴリズム、1994)とGrover algorithm(グローバー アルゴリズム、1996)は量子計算理論の代名詞的アルゴリズム2大トップで、現代暗号系の根幹を脅かす理論的存在として広く認知される。Peter W. Shor(1959年生、AT&T Bell Labs→MIT教授)が1994年AT&T Bell Labs在籍時に発表した「Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer」で、整数 N の素因数分解を古典計算 O(exp(N^(1/3))) の劣指数時間 → 量子計算 O((log N)^3) の多項式時間に高速化、これは RSA(Rivest-Shamir-Adleman 1977)・ECC(Elliptic Curve Cryptography)・DH(Diffie-Hellman 1976) 等の公開鍵暗号系を全て破壊する革命的成果。Lov K. Grover(1961年生、Bell Labs)が1996年「A fast quantum mechanical algorithm for database search」で発表した Grover algorithm は、非構造化データベースから特定要素検索を古典 O(N) → 量子 O(√N) に √N加速、AES-128(古典2^128 → 量子2^64)/SHA-256(2^256 → 2^128) 等の対称鍵暗号・ハッシュ関数の実効強度を半減させる。実用的脅威レベルでは: 2048-bit RSA解読には Shor algorithm + 約4,000 logical qubit + 約2,000万物理qubit(Surface Code d=21使用時) + 数日数週間実行時間が必要と推定(2024年Microsoft研究)、2030年代後半2040年代に最速で実現可能、量子安全(Post-Quantum Cryptography、NIST 2024年8月正式標準化 ML-KEM/ML-DSA/SLH-DSA)への移行が現代暗号最大の課題。\n\n## 主な特徴・仕組み\n\n- Shor (1994): 素因数分解 O(exp) → O((log N)^3)、多項式高速化\n- Grover (1996): 非構造化探索 O(N) → O(√N)、√N高速化\n- Shorコア: Quantum Fourier Transform + 順序 finding(modular exponentiation)\n- Groverコア: Oracle + Diffusion operator のn回反復、Amplitude増幅\n- RSA 2048脅威: 4,000 logical qubit + 約2,000万物理qubit + 数日実行\n- AES脅威: AES-128 → 実効2^64、AES-256 → 実効2^128(まだ安全)\n- PQC 移行: NIST 2024-08 ML-KEM/ML-DSA/SLH-DSA 正式標準化\n- 時期見込み: RSA脅威化 2030-2040、PQC2025-2030移行推奨\n\n## スペック比較表\n\n| アルゴリズム | 古典計算量 | 量子計算量 | 影響 | 必要qubit |\n|-------------|------------|------------|------|-----------|\n| 素因数分解 | exp(N^(1/3)) | (log N)^3 | RSA破壊 | 4,000 logical (RSA-2048) |\n| 離散対数 | exp(N^(1/3)) | (log N)^3 | DH/DSA破壊 | 2,000-4,000 logical |\n| ECC ECDLP | exp(√N) | (log N)^3 | ECC破壊 | 2,000 logical (P-256) |\n| 非構造化探索 | N | √N | AES実効半減 | 数百 logical |\n| 衝突発見(BB84) | √N | N^(1/3) | ハッシュ強度半減 | 数千 logical |\n| HHL (連立方程式) | poly(N) | log(N) (条件下) | 機械学習加速 | 数百-1000 logical |\n| QAOA | - | - | 組合せ最適化近似 | 100-1000 |\n| VQE | - | - | 化学・材料 | 100-1000 |\n\n## 具体例・対応製品\n\n- Shor 1994論文: arxiv.org/abs/quant-ph/9508027、AT&T Bell Labs\n- Grover 1996論文: STOC 1996、Bell Labs Lov Grover\n- NIST PQC Standards (2024-08): ML-KEM(鍵交換)/ML-DSA(署名)/SLH-DSA(署名)\n- Microsoft Azure Quantum 2024 Whitepaper: RSA-2048解読 200万物理qubit試算\n- Cloudflare PQC試験: 2024年からML-KEM TLS 1.3 大規模実験\n\n## 自作PCでの選び方・注意点\n\nPost-Quantum 暗号対応PC構築例: (A)個人¥150,000構成: M3 Mac mini + macOS Sequoia 15+ (2024年ML-KEM対応開始予定) + 1Password Passkey、PQ移行先取り、(B)企業¥500,000構成: Linux Server + OpenSSL 3.5+ (PQC実装) + ML-KEM対応TLSライブラリ、(C)国家機密¥10,000,000+構成: HSM(Hardware Security Module) + PQC専用実装 + Quantum Key Distribution(BB84)。RSA 2048-bitは2030年代後半まで実用上安全、ただし Harvest Now Decrypt Later 攻撃(現在暗号化通信を保存し将来量子復号)の脅威があり、機密性10年以上必要なデータは2025-2027年で PQC移行推奨。NIST FIPS 203/204/205 (2024-08正式) で実装ガイドライン確定、AWS/Azure/GCP/Cloudflareが2024-2026年TLS 1.3 PQC ハイブリッド対応開始。\n\n## 関連用語との違い\n\nHHL Algorithm (Harrow-Hassidim-Lloyd 2009): 連立一次方程式の量子高速化、機械学習加速候補。Shor/Groverと比べ条件厳しく実用化遠い。\n\nVQE/QAOA: 変分量子アルゴリズム、化学・最適化用 NISQ向け。Shor/Grover はFTQC前提、VQE/QAOAは現在のNoisy hardwareで実行可だが収束保証弱い。\n\n## よくある質問(FAQ)\n\nQ1: いつ RSA 危険?\nA: 4,000+ logical qubit 安定実現 + 数百万物理qubit + 数日実行時間、Google/IBM ロードマップ最速2030年代後半、現実的脅威化2040年代。Harvest Now Decrypt Later 対策で2027年までPQC移行推奨。\n\nQ2: AES-256 安全?\nA: 安全、Grover algorithm でも実効2^128強度、対称鍵256bitなら量子計算でも数百万年。AES-128は実効2^64で危険、2026-2030年でAES-256への移行推奨。\n\nQ3: NIST PQC選ぶ?\nA: 2024-08標準化 ML-KEM(鍵交換、CRYSTALS-Kyber後継)・ML-DSA(署名、CRYSTALS-Dilithium後継)・SLH-DSA(署名、SPHINCS+後継)が公式選択肢。OpenSSL 3.5/AWS/GCP/Azureで2025-2026年実装進行。\n\n## まとめ\n\n- Shor(1994)RSA/ECC素因数分解多項式高速化\n- Grover(1996)非構造化探索 √N加速\n- 2048-bit RSA 解読 4,000 logical qubit + 2030-2040年\n- AES-128 → 実効2^64で半減、AES-256は安全\n- NIST PQC 2024-08標準化、2027年移行推奨