ショアの素因数分解アルゴリズム

なぜ素因数分解が「周期」の問題になるのか

ショアのアルゴリズムの核心は、量子回路そのものではなく 「素因数分解を周期発見に帰着する」古典的な数論のトリック にあります。この帰着さえ理解すれば、量子部分は「周期を高速に見つける道具」として位置づけられます。

合成数 N（例えば RSA 法）を分解したいとします。N と互いに素な整数 a（1 < a < N）を1つ選び、次の数列を考えます。

a^0, a^1, a^2, a^3, ...  （すべて mod N）

a と N が互いに素なら、この数列は必ず周期的になります。ある最小の正整数 r が存在して a^r ≡ 1 (mod N) が成り立ち、この r を a の位数（order） と呼びます。位数 r こそがショアが量子的に求める量です。

位数 r から素因数を取り出す

なぜ位数を知ると分解できるのか。r が 偶数 で、かつ a^(r/2) が -1 と合同でない（a^(r/2) ≢ -1 (mod N)）という2条件が満たされたと仮定します。位数の定義より a^r ≡ 1 なので a^r - 1 ≡ 0 (mod N)、これを因数分解すると次のようになります。

a^r - 1 = (a^(r/2) - 1)(a^(r/2) + 1) ≡ 0  (mod N)

つまり N は積 (a^(r/2) - 1)(a^(r/2) + 1) を割り切ります。ここで a^(r/2) ≢ ±1 (mod N) なら、N はどちらの因子も単独では割り切れません。したがって N の素因数は2つの因子に分かれて入り込んでおり、最大公約数を取るだけ で非自明な因数が得られます。

p = gcd(a^(r/2) - 1, N)
q = gcd(a^(r/2) + 1, N)
→ p, q は 1 でも N でもない N の約数（＝素因数の一部）

gcd はユークリッドの互除法で高速に計算できます。ランダムな a に対しこの2条件が成立する確率は 1/2 以上あることが知られ、失敗しても a を選び直して数回試せば高い確率で成功します。

ここまでは すべて古典計算 で、しかも高速（多項式時間）です。唯一、指数関数的に難しいのが「位数 r を求める」ステップであり、ショアの真の貢献はこの1点を量子的に解いたことにあります。

量子位相推定で位数を求める

位数発見は、量子位相推定（Quantum Phase Estimation, QPE） の一種として実装します。QPE は「あるユニタリ演算 U の固有値 e^(2πiθ) の位相 θ を、高精度で読み出す」汎用手続きです。位数発見では、次の モジュラ乗算ユニタリ を対象にします。

U|y⟩ = |a·y mod N⟩     （y は 0 以上 N 未満の整数を符号化した状態）

この U の固有状態は、位数 r と整数 s（0 ≤ s < r）を用いて表せ、対応する固有値の位相はちょうど s/r になります。

U|u_s⟩ = e^(2πi · s/r) |u_s⟩

つまり U の位相 θ = s/r を推定できれば、その分母から r が復元できます。QPE の回路は2つのレジスタから成ります。

手続きは次の4段階で進みます。各段の「何を計算しているか」を追うのがポイントです。

1. 重ね合わせ生成 : カウントレジスタにアダマール変換をかけ、
   0..2^t-1 の全整数 x を等振幅で重ね合わせる。
2. 制御モジュラ冪 : x を制御に U を x 回適用し、下位に a^x mod N を作る。
   → 状態は Σ_x |x⟩ |a^x mod N⟩ の重ね合わせ（全 x を一度に計算）。
3. 逆量子フーリエ変換 : カウントレジスタに逆 QFT をかけ、
   周期構造を「位相 s/r 付近の鋭いピーク」に変換する。
4. 測定 : カウントレジスタを測定し、s/r に近い 2^t·s/r を得る。

量子フーリエ変換が「周期」を「位相」に変える

なぜ逆 QFT で周期が読み出せるのか。離散フーリエ変換は、時間領域の周期性を周波数領域のピークに写す 変換です。量子版の QFT は、これを量子ビット上で n 桁に対し O(n^2) ゲート（古典 FFT の O(n·2^n) 相当を遥かに凌ぐ）で実行します。QFT の作用は基底状態 |x⟩ を次のように写します。

QFT|x⟩ = (1/√M) · Σ_{k=0}^{M-1} e^(2πi · x·k / M) |k⟩     （M = 2^t）

ステップ2の後、下位レジスタがある値 a^x0 mod N に「事実上」定まると、上位レジスタには x0, x0+r, x0+2r, ... という 周期 r の等間隔な x だけが振幅を持ちます。この周期列に逆 QFT をかけると、位相因子 e^(2πi·x·k/M) の総和は、k が M/r の整数倍付近のときだけ位相が揃って強め合い、それ以外では打ち消し合います。結果、測定で得られる k は近似的に次を満たします。

k / M ≈ s / r     （s は 0..r-1 のいずれか、未知）

ここから r を取り出すのが 連分数展開 です。観測した分数 k/M を連分数に展開して近似分数（収束分数）を求めると、分母に真の r（または r の約数）が現れます。t ≈ 2·log2(N) 桁取っておけば、この復元が高確率で成功することが保証されます。得た候補 r は古典側で a^r ≡ 1 (mod N) を検算し、外れなら測定をやり直します。

古典との計算量差 ── ここが破壊力の源泉

古典の最良既知アルゴリズムである 一般数体ふるい（GNFS） の計算量は、桁数 n = log N に対して準指数時間（sub-exponential）です。一方ショアは n の 多項式時間 で走ります。

差の意味は「鍵長を伸ばす防御が効くかどうか」に出ます。古典が準指数なら、鍵を2倍にすれば攻撃コストは天文学的に跳ね上がり、実質安全を保てます。しかしショアでは、計算量が桁数の多項式でしか増えないため、RSA の鍵を長くしても攻撃コストが緩やかにしか伸びず、十分な量子ビットさえあれば破れてしまう——これが公開鍵暗号にとって致命的なのです。

実機での制約と耐量子暗号への含意

理論上は多項式時間でも、実機での実行には巨大なハードルがあります。RSA-2048 を破るには、制御モジュラ冪を誤りなく実行するために 数千の論理量子ビット が必要で、量子誤り訂正を考慮すると 数百万の物理量子ビット が要ると見積もられています。現行の量子プロセッサ（数百物理量子ビット規模）とは桁が大きく隔たっており、実際に破られた記録は小さな合成数に限られます。

この「収穫後復号（harvest-now, decrypt-later）」——今のうちに暗号文を収集し、将来の量子計算機で復号する——という脅威から、格子問題など量子でも難しいとされる問題に基づく 耐量子暗号（PQC） への移行が、現実の暗号運用で急務になっています。暗号方式の全体像は /security/ 側で扱います。

まとめ

• ショアのアルゴリズムは 素因数分解を「a^x mod N の位数（周期）r の発見」へ帰着 する数論のトリックが起点で、r が偶数かつ a^(r/2) ≢ ±1 なら gcd(a^(r/2)±1, N) で非自明な因数が取れる。
• 位数発見は 量子位相推定 で解く。モジュラ乗算ユニタリの固有値位相が s/r になることを利用し、逆量子フーリエ変換 で周期を位相ピークに変え、連分数展開 で r を復元する。
• 量子並列性そのものではなく、周期構造を強め合う干渉の設計 が本質。全 x の重ね合わせを作っても、干渉なしには意味ある値は測れない。
• 古典最良の GNFS が 準指数時間 なのに対し、ショアは 多項式時間。この差ゆえ鍵長の増強が防御にならず、RSA・DH・ECC が横並びで危殆化するため、耐量子暗号への移行が必要になる。