出典検証済みレベル 4
ショアのアルゴリズム
ショアのアルゴリズムは大きな整数を多項式時間O((log N)³)で因数分解し、RSA暗号を脅かします。
どういう意味か
因数分解を量子フーリエ変換を使った周期発見に帰着させます。ポスト量子暗号研究の動機です。日常のたとえ
秘密のリズムを見つけるようなもの。
金庫の共鳴周波数を見つけるようなもの。
よくある誤解
- すべての暗号を即座に破るわけではありません。
- 現在の量子コンピュータでは実行できません。
要点
- O((log N)³)で整数因数分解。
- QFTによる周期発見に帰着。
- ポスト量子暗号の動機。
理解度チェック
ショアのアルゴリズムが因数分解を帰着させる問題は？
- A.行列乗算
- B.周期発見
- C.グラフ彩色
- D.ソート
答えを見る
答え: B. 周期発見
理由: 因数分解を周期発見に帰着させます。
前提となる概念
一次資料: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.