Shor分解士

周期発見で合成数を素因数分解する量子手順を、ステップ実行で辿る。

Shor アルゴリズム (1994): 合成数 N の因数分解を 多項式時間 で。RSA崩壊の脅威。
手順: ① 1<a<N をランダムに選択 ② gcd(a,N)≠1 なら因数発見 ③ そうでなければ周期 r = order(a mod N) を 量子フーリエ変換 で発見 ④ r が偶数かつ a^(r/2) ≢ -1 (mod N) なら、gcd(a^(r/2)±1, N) が 非自明な因数。

N (target) 15 a - r (周期) - Stage 0/5

分解する N

手順

計算ログ

N をセットして「次へ」

操作

N を選び、次へ ▶ でステップごとに進む。① ランダム a 選択 → ② gcd ショートカット → ③ 量子周期発見 (この実装では古典シミュレート: a, a², a³ ... mod N) → ④ QFT で周期抽出 → ⑤ 古典後処理。
本物の量子計算機では ③ が量子重ね合わせと QFT で多項式時間。キャンバスには周期関数がプロットされ、QFT の結果が縦線として表れる。