因数分解を位数発見に帰着する

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.1　★★★ 位数 $r$ が偶数で $a^{r/2}\not\equiv-1$ なら $\gcd(a^{r/2}\pm1,N)$ が因数になる。でたらめに選んだ $a$ で半分以上の確率でそうなる

$N$ を2つ以上の素数の積とする。$N$ を素因数に分ける問題は、桁数 $n=\lceil\log_2N\rceil$ について多項式時間で解く古典のアルゴリズムが知られていない。この難しさを安全性の根拠に置いたのが RSA 暗号である¹1R. L. Rivest, A. Shamir and L. Adleman (1978), Commun. ACM 21, 120。下の脚注へ閉じる。P. W. Shor は 1994 年に、量子コンピュータを使えば $\mathcal{O}(n^3)$ 程度の手間で因数分解できることを示した²2P. W. Shor (1994), Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124。詳しい版は P. W. Shor (1997), SIAM J. Comput. 26, 1484。下の脚注へ閉じる。

この章が選ぶ問題は、$N$ と互いに素な整数 $a$ について、$a^r\equiv1\pmod N$ を満たす最小の正の整数 $r$（$a$ の位数）を求める問題である。因数分解は、古典の計算だけで位数を求める問題に帰着する（6.3.1 節）。量子計算を使うのは位数を求める部分だけで、「$y$ に $a$ を掛けて $N$ で割った余りを取る」ユニタリ $U_a$ の固有値が $\mathrm{e}^{2\pi\mathrm{i} s/r}$ の形をしていることから、前の章の位相推定（第6部第2章）で $s/r$ の近似値が読める（6.3.2 節）。近似値から分母 $r$ を取り出す操作は連分数で行い（6.3.3 節）、ここで再び古典の計算に戻る。6.3.4 節で1回の実行が成功する確率と回路の大きさを数え、RSA の 2048 ビットの鍵に要る資源の現在の見積もりを引く。

この巻の背骨である相対エントロピーとの縁は、6.3.5 節に1つだけ置く。位相推定の直前の状態を計算基底でそのまま測ると、結果は周期について何も教えない（相互情報量が $0$）。同じ状態に逆 Fourier 変換を当ててから測ると、相互情報量はほぼ $\ln r$ になり、出力の分布は一様分布から $D$ の分だけ離れる。周期の情報は状態の位相に書かれていて、逆 Fourier 変換はその位相を測定で読める基底へ移す操作である。6.3.6 節では、信号処理の授業の離散 Fourier 変換と、暗号の授業の RSA を、この章の式と並べる。

この章の対数は自然対数（nat）とし、ビットで数えるときは $\log_2$ と書く。$N$ は奇数で、素数の累乗でないとする（偶数なら $2$ で割れ、$N=p^k$ なら $N^{1/k}$ を $k=2,\dots,n$ について古典の計算で調べれば見つかる）。第1のレジスタの量子ビットの数を $t$、測定で得る整数を $m\in\{0,1,\dots,2^t-1\}$ と書く。位相推定の流儀は前の章に合わせ、$t$ 量子ビットの量子 Fourier 変換を $| x \rangle \mapsto2^{-t/2}\sum_{k}\mathrm{e}^{2\pi\mathrm{i} xk/2^t}| k \rangle$ とする（第6部第2章の式 (6.2.1) と同じ符号）。Euler の関数（$N$ 以下で $N$ と互いに素な正の整数の個数）を $\phi(N)$ と書き、位相の $\varphi$ と字形で分ける。

1の平方根で $\pm1$ でないもの

$N$ と互いに素な $a$（$1\le a<N$）を1つ選び、その位数 $r$ が分かったとする。$r$ が偶数なら $x\coloneqq a^{r/2}\bmod N$ は

$$x^2\equiv a^r\equiv1\pmod N$$

を満たす。つまり $x$ は「$N$ を法とした1の平方根」である。$N$ が素数なら1の平方根は $\pm1$ しかないが、$N$ が合成数なら他の平方根がある。$r$ は位数（最小）なので $x\not\equiv1$ である。さらに $x\not\equiv-1$ なら、

$$(x-1)(x+1)\equiv0\pmod N,\qquad x-1\not\equiv0,\quad x+1\not\equiv0\pmod N\tag{6.3.1}$$

となる。$N$ は積 $(x-1)(x+1)$ を割り切るのに、どちらの因子も割り切らない。したがって $N$ の素因数の一部は $x-1$ に、残りは $x+1$ に入っていて、$\gcd(x-1,N)$ と $\gcd(x+1,N)$ はどちらも $1$ でも $N$ でもない約数になる。最大公約数は Euclid の互除法で $\mathcal{O}(n^3)$ 程度のビット演算で求まるので、ここまでの手間は古典の計算として小さい。

たとえば $N=15$、$a=7$ では $7^1=7$、$7^2=49\equiv4$、$7^3\equiv28\equiv13$、$7^4\equiv91\equiv1$ で、位数は $r=4$ である。$x=7^2\bmod15=4$ は $\pm1$ でないので、$\gcd(3,15)=3$ と $\gcd(5,15)=5$ が因数として出てくる。

でたらめな $a$ がうまくいく確率

うまくいかないのは、$r$ が奇数のときと、$a^{r/2}\equiv-1$ のときである。$N=15$ の $a=14$ は $14\equiv-1$ なので $r=2$、$a^{r/2}\equiv-1$ で失敗し、$a=1$ は $r=1$ で失敗する。失敗する $a$ が少ないことは、次の定理が保証する。

$N=15$ では $N$ と互いに素な $a$ が $\phi(15)=8$ 個あり、そのうち $a=1,14$ を除く6個で成功する（割合 $3/4$）。$N=21$ では12個のうち6個（$1/2$、下界の等号）、素因数を3個持つ $N=105$ では $0.875\ge3/4$ である。1回の試行で半分以上の確率で成功するので、$a$ を選び直して $\ell$ 回試せば失敗の確率は $2^{-\ell}$ 以下になる。残る仕事は位数 $r$ を求めることだけで、ここに古典の速いアルゴリズムが知られていない。