授業で習った形との対応：離散 Fourier 変換と RSA 暗号

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.6　★★ 周期 $r$ の列の離散 Fourier 変換は $L/r$ の倍数に立つ。RSA の復号は、因数分解を経ずに暗号文の位数からもできる

周期の列の離散 Fourier 変換

信号処理の授業では、長さ $L$ の列 $f_x$（$x=0,\dots,L-1$）の離散 Fourier 変換を $\hat f_k=\sum_xf_x\mathrm{e}^{-2\pi\mathrm{i} kx/L}$ と書き、周期 $r$ の列で $r$ が $L$ を割り切るなら $\hat f_k$ は $k$ が $L/r$ の倍数のところにだけ値を持つことを習う。$f_{x+r}=f_x$ から $\hat f_k=\mathrm{e}^{-2\pi\mathrm{i} kr/L}\hat f_k$ が出て、$kr/L$ が整数でない $k$ では $\hat f_k=0$ になるからである。$r$ が $L$ を割り切らないときは、$k\approx Ls/r$ の近くに幅を持った山が立つ（スペクトルの漏れ）。

量子 Fourier 変換は、この変換を状態の振幅に当てたもので、式 (6.3.8) の山はスペクトルの漏れを含めて古典の離散 Fourier 変換の山と同じ形をしている。違いは2つある。古典の高速 Fourier 変換は長さ $L=2^t$ の列全部を入力に取るので $\mathcal{O}(L\log L)=\mathcal{O}(t2^t)$ の手間がかかり、出力として $L$ 個の係数全部を返す。量子 Fourier 変換は $\mathcal{O}(t^2)$ 個のゲートで済むが、出力として返すのは $\lvert \hat f_k\rvert ^2$ に比例する確率で選ばれた1つの $k$ だけである。周期を求める問題では山の位置1つで足りるので、この「1つしか返さない」制約が問題にならない。

RSA 暗号

暗号の授業での RSA は次の形である。素数 $p$、$q$ を選び $N=pq$、$\phi(N)=(p-1)(q-1)$ とし、$\gcd(e,\phi(N))=1$ の $e$ と、$ed\equiv1\pmod{\phi(N)}$ の $d$ を作る。$(N,e)$ を公開し、平文 $x$ を $c=x^e\bmod N$ で暗号化する。Euler の定理 $x^{\phi(N)}\equiv1$（$\gcd(x,N)=1$）から $c^d=x^{ed}=x^{1+k\phi(N)}\equiv x$ で復号できる。$d$ を求めるには $\phi(N)$、したがって $p$、$q$ を知る必要があり、これが「因数分解が難しければ安全」の根拠である。

Shor のアルゴリズムで $N$ を因数分解すれば $\phi(N)$ と $d$ が求まる。この章の言葉では、もっと直接の破り方もある。暗号文 $c$ の位数 $r=\operatorname{ord}_N(c)$ を位数発見の回路で求めたとする。$x$ の位数 $r_x$ は $\phi(N)$ を割り切り、$e$ は $\phi(N)$ と互いに素なので $\gcd(e,r_x)=1$ で、$c=x^e$ の位数は $r_x$ に等しい。したがって $d'\coloneqq e^{-1}\bmod r$ を取ると

$$c^{d'}=x^{ed'}=x^{1+kr}\equiv x\pmod N\tag{6.3.16}$$

で、因数分解を経ずに平文が戻る。RSA の安全性は「$N$ を法とした掛け算の位数が求められない」ことに依っていて、位数が求められれば、この前提は成り立たなくなる。