応用数学解説

文献あり

量子コンピュータにおける素因数分解(4): アルゴリズムの方針 & 関連定理

初等整数論,量子コンピュータ,Shorのアルゴリズム

はじめに

この記事は量子コンピュータによる素因数分解のアルゴリズムである「Shorのアルゴリズム」の解説記事第4回目です。1-3回目は以下：

本記事ではShorのアルゴリズムの基本的な方針の説明、およびこれに関連した整数論まわりの定理に関して述べます。実はShorのアルゴリズムの基本方針はそれほど難しくないです。

以下「多項式時間で計算可能」とは、整数$i$を2進数表示したとき、計算量がその桁数の多項式で表されるという意味です。

本記事はRef.Hosoyaを元に書かれています。

Shorのアルゴリズムの基本的な方針

整数$N$を因数分解します。

$N$未満で$N$と互いに素である整数$x$を適当に選びます。そして
\begin{align} \hspace{1.5cm}x^r\equiv 1 \text{ mod }N\tag{1} \end{align}
を満たす$r$を探します。このような$r$で最も小さいものは位数（order）と呼ばれますが、ここでは必ずしも最小である必要はないです。

$r$が求まり、かつそれが偶数だったとしましょう。偶数になるのは偶然に頼ることになります。もし$r$が偶数だったら、$x^r-1$を以下のように因数分解できます：
\begin{align} \hspace{1.5cm} x^r-1=(x^{r/2}+1)(x^{r/2}-1) \end{align}

よってEq.(1)より

\begin{align} \hspace{1.5cm}(x^{r/2}+1)(x^{r/2}-1)=a\times N \ \ \ (a\text{は正の整数}) \end{align}
です。いま正の整数$n$と$m$の最大公約数を$\text{gcd}(n,m)$で表しましょう（greatest common divisor, gcd）。上の式より、$x^{r/2}\pm 1$が$N$の倍数でない限り、$\text{gcd}(x^{r/2}\pm 1,N)$のどちらかは$N$の因数を与えます\。

ということで、もしも以下の3つの条件：

素因数分解が多項式時間で行える条件

Eq.(1)を満たす$r$を多項式時間で求めることができる
最大公約数(gcd)を多項式時間で求めることができる
試行錯誤が必要な部分：「$N$と互いに素な$x$を選ぶ」「$r$が偶数」「$x^{r/2}\pm 1$はどちらも$N$の倍数ではない」は多項式時間での計算を可能にするほど十分高確率で起きる

を満たすことができるなら、素因数分解が多項式時間で行えることになります。

そして量子コンピュータを用いればこれらを満たすことができます。正確に言うと、量子コンピュータが必要なのは1.のみです。以下各条件が満たされることに関して述べます。

条件1.に関して

1.に関しては、3回の記事で議論してきたべき剰余$a^x \text{ mod }N$を計算する量子回路および量子フーリエ変換を行う量子回路で行えます。Shorのアルゴリズムにおいて量子コンピュータが担う課題は、Eq.(1)を満たす$r$の推定です。これはまた今後の記事で述べます。

条件2.に関して

2.はユークリッドの互除法により多項式時間で行えるので量子コンピュータは必要ありません。最大公約数を求めるのに素因数分解はいりません。よく知られているように以下の定理が成立します：

2つの$a,b\in\mathbb{N} \ \ (a\ge b)$について、$a$の$b$による剰余を$r$とすると
\begin{align} \hspace{1.5cm}\text{gcd}(a,b)=\text{gcd}(b,r) \end{align}
が成立する。

$\text{gcd}(a,b)=m,\ \text{gcd}(b,r)=n$とする。

$a$割る$b$の商を$q$とする。すなわち
\begin{align} \hspace{1.5cm} a=bq+r \tag{thm1.1}\\ \therefore r=a-bq \tag{thm1.2} \end{align}
とする。$m$は$a$と$b$のgcdなので、Eq.(thm1.2)より$m$は$r$の公約数（common divisor, cd）である。よって$m$は$b$と$r$のcdである。ここで$\text{gcd}(b,r)=n$だから
\begin{align} \hspace{1.5cm} m\le n \tag{thm1.3} \end{align}
一方$n$は$b$と$r$のgcdなので、Eq.(thm1.1)より$n$は$a$と$b$のcd。そして$\text{gcd}(a,b)=m$なので
\begin{align} \hspace{1.5cm} n\le m \tag{thm1.4} \end{align}
Eq.(thm1.3)(thm1.4)より$m=n$。ゆえに$\text{gcd}(b,r)=\text{gcd}(a,b)$。${}_\blacksquare$

これに基づいた最大公約数の求め方がユークリッドの互除法です：

ユークリッドの互除法その1

$a,b \ (a\ge b)$のgcdを求めるには、まず$a\text{ mod }b=c$を計算する。そして$b$を$a$と、$c$を$b$と呼び直し、同様に$a\text{ mod }b=c$を計算する。これを繰り返し、$c$がゼロになったときの$b$が最初の$a,b$のgcd。

具体的に$\text{gcd}(135,54)$を計算します。$135 \text{ mod }54=27$、$54 \text{ mod }27 =0$なので$\text{gcd}(135,54)=27$です。

「ユークリッドの互除法その1」は以下と等価です：

ユークリッドの互除法その2

$a-b$と$b$を作る。そして大きい方から小さい方を引く。「大きい方から小さい方を引いたもの」と$b$のうち、大きい方を$a$、小さい方を$b$と呼び直し、さらに$a-b$と$b$を構成する。これを繰り返すと有限回で$b=0$となるが、ゼロになる直前の$b$の値がgcd。

具体的に$\text{gcd}(135,54)$を計算します。$a-b=135-54=81$と$b=54$では$81$が大きいので、$81-54=27$と$54$を得る。$a=54$、$b=27$と呼び直して$a-b=27$と$b=27$を得る。$27-27=0$なので、$27$がgcd。

このようなgcdの計算は、計算過程を見てもわかるように高速に（=多項式時間で）実行できます。これはShorのアルゴリズムにおける重要な事実です。

条件3.に関して

まず「$N$と互いに素な正の整数$x \ (x< N)$を選ぶ」に関して。オイラー関数を導入します：

オイラー関数$\varphi(n):$ 1以上n以下の自然数で$n$と互いに素なものの個数（※1は1以外とは常に素）

「$N$と互いに素な$x$を選ぶ」が高確率で成功するのは以下の定理によります（Ref.Hosoyaから引用。証明等はRef.Wikipediaから辿ってみてください）：

$\varphi(n)$は$e^{-\gamma}n/\log\log n$より大きい

よって$\log \log n$回程度試行すれば、1回くらいは$n$と互いに素な数に行き当たります。

「Eq.(1)を満たす$r$が偶数」「$x^{r/2}\pm 1$はどちらも$N$の倍数ではない」に関して高確率で成功することは以下の定理で保証されます（Ref.Hosoyaから引用。証明は例えばRef.Ekertにあるようです）：

与えられた奇数$N$が素数のべきでない時に、$N$より小さい$N$と互いに素な数たち$\{x\}$のうちで、その位数$r$が偶数でしかも$x^{r/2}\neq \pm 1\ \mathrm{mod}\ N$であるような$x$は半数以上ある:
\begin{align} \hspace{1.5cm} P(r:\mathrm{even},\ x^{r/2}\neq \pm 1\ \mathrm{mod} \ N)\ge 1/2 \end{align}

これに関してコメントを加えておきます。いま位数を改めて$r_{\rm min}$とします。このとき$x^{n r_\text{min}}=1\text{ mod }N,\ n\in \mathbb{N}$であることはすぐわかります。すなわち$r=nr_\text{min}$は$x^r=1\text{ mod }N$を満たします。ここで$n$が偶数だったとしましょう。このとき$x^{nr_\text{min}/2}=x^{\alpha r_\text{min}},\ \alpha=n/2\in \mathbb{N}$なので、$x^{nr_\text{min}/2}=1\text{ mod }N$です。これは「$x^{r/2}\pm 1$はどちらも$N$の倍数ではない」に反します。すなわち
\begin{align} \hspace{1.5cm} r=nr_\text{min}, \ n\in \mathbb{N}\text{ は }x^r=1\text{ mod }N\text{ を満たすが、}n\text{が偶数のとき}N\text{の素因数を導くには不適切である} \end{align}
ということが言えます。一方位数の奇数倍の$r$については素因数を計算するのに適しています。いづれにせよ、定理3および上の考察より、「Eq.(1)を満たす$r$が偶数」「$x^{r/2}\pm 1$はどちらも$N$の倍数ではない」は、多項式時間の計算を邪魔しないほど高確率で起きます。

結論

以上より、条件2.3.は満たされることがわかりました。条件1.「$N,x$が与えられたとき位数$r$を多項式時間で求めることができる」が達成できることは今後の記事で述べます。

おしまい & つづく。${}_\blacksquare$

${}$
${}$

Appendix: Shorのアルゴリズムまわりの定理

以下、Shorのアルゴリズムに（多かれ少なかれ）関連する定理を適当に挙げていきます。証明はあったりなかったりします。

オイラー関数の具体的な表示

整数$n$のオイラー関数$\varphi(n)$は$n$の素因数分解を用いて表すことができますWikipedia:

$p$が素数のとき$\varphi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right)$
$m,n$が互いに素のとき$\varphi(mn)=\varphi(m)\varphi(n)$
これらより、$n=\prod_{k=1}^d p_k^{e_k}$のように素因数分解したとき
$$ \varphi(n)=n\prod^d_{k=1}\left(1-\frac{1}{p_k}\right) $$
と表せる。

原始根

素数$p$に対して位数が$p-1$であるような元$r$のことを$p$の原始根とよぶ。

素数$p$には原始根$r$が必ず存在する。

証明は例えば原始根（青空学園数学科）参照のこと。

$r$に関して、$r,r^2,\cdots,r^{p-1}$を$p$でわった余りはすべて異なり、$1$から$p-1$までを巡回する。

以下原始根の定義と具体例(高校生向け) 高校数学の美しい物語より。

$r$を原始根とし、かつ$r^n\ (n=1,2,\cdots,p-1)$の中に$p$で割った余りが等しいものがあるとする。いま$\text{mod　} p$で$r^n=r^m \ (p-1\ge m>n)$とする。このとき
\begin{align} \hspace{1.5cm} r^n(r^{m-n}-1)=0 \ (\text{mod }p) \end{align}
だが、$r^n$は$p$と互いに素だから$r^{m-n}-1=0\text{ mod }N$である。しかし$m-n< p-1$なのでこれは原始根の定義に反する。ゆえに$r^n \ (n=1,2,\cdots,p-1)$の中に$p$で割った余りが等しいものはない。ところが$r^n$は$p-1$個存在するので、$p$で割った余りは$1$から$p-1$を巡回する。${}_\blacksquare$

中国式剰余定理

$n_1$と$n_2$が互いに素とする。このとき
$$ \hspace{1.5cm}x\equiv a_1 \ (\mathrm{mod} \ n_1),\ x\equiv a_2 \ (\mathrm{mod} \ n_2) $$
の両方を満たす整数$x$が$0$以上$n_1n_2$未満の範囲にただ一つ存在する。

解の唯一性
2つ以上の解が存在するとする。これらを$x,y \ (x\neq y)$とする。$x-y$は$n_1,n_2$どちらの倍数でもあり、かつ$n_1,n_2$は互いに素なので、$x-y$は$n_1n_2$の倍数。しかし$x,y$は共に$n_1n_2$未満であるから、$x-y$はゼロになる、すなわち$x=y$。これは仮定に反する${}_\blacksquare$
解の存在
具体的に解を構成する。$n_1,n_2$は互いに素なので、ベズーの定理より（後述）
\begin{align} \hspace{1.5cm} n_1X+n_2Y=1 \end{align}
を満たす整数$X,Y$が存在する。ゆえに
\begin{align} \hspace{1.5cm} n_2Y&\equiv 1 \ (\text{mod }n_1),\\ n_1X&\equiv 1 \ (\text{mod }n_2) \end{align}
である。ゆえに$x'=a_1n_2Y+a_2n_1 X$とすれば
\begin{align} \hspace{1.5cm} x'\equiv a_1 \ (\text{mod }n_1)\\ x'\equiv a_2 \ (\text{mod }n_2) \end{align}
となり、$x'$は$n_1n_2$未満という条件以外の満たすべき性質をもつ。$x'$を$n_1n_2$でわった余りにしておけば、上記性質を満たしかつ$n_1n_2$未満という満たすべき条件をもつ数が求まる。${}_\blacksquare$

ベズーの定理

以下一次不定方程式ax+by=cの整数解（高校数学の美しい物語）等より。

$a,p$が互いに素なとき、$a,2a,3a,\cdots,(p-1)a$を$p$で割った余りはすべて異なる

正の整数$i,j$に関し、$ia$と$ja$（$i>j$）を$p$でわった余りが同じと仮定する。
このとき$(i-j)a$は$p$の倍数。
しかし$1\le i-j < p$かつ$a$と$p$は素なので矛盾。${}_\blacksquare$

$ax+by=1$が整数解をもつ$\leftrightarrow$$a$と$b$は互いに素

→の証明：対偶をとる。$a$と$b$が互いに素でないとき、$a,b$のcdの1つを$d\ge 2$とおくと$ax+by$は$d$の倍数となり解を持たない。
←の証明：$a,b$が互いに素なとき、$a,2a,3a,\cdots,(b-1)a$を$b$で割った余りはすべてことなるので（定理7より）、余りが1となるようなものが存在する。それを$ma$とおき、$b$で割った商を$n$とおくと
$$\hspace{1.5cm}ma=bn+1$$
つまり$am-bn=1$となり$(m,-n)$は整数解になっている。${}_\blacksquare$

$x,y$に関する不定方程式$ax+by=c$が整数解をもつ $\leftrightarrow$ $c$は$\mathrm{gcd}(a,b)$の倍数

→の証明：$a,b$は$\mathrm{gcd}(a,b)$の倍数なので整数解$m,n$に対して$am+bn$も$\text{gcd}(a,b)$の倍数。つまり$c$は$\text{gcd}(a,b)$の倍数。
←の証明：定理8の結果から$pm+qn=1$は整数解をもつ。両辺を$\text{gcd}(a,b)$倍して、
$$ \hspace{1.5cm}am+bn=\text{gcd}(a,b) $$
も整数解をもつことがわかる。よって$c$が$\text{gcd}(a,b)$の倍数のとき、両辺を適当に整数倍すれば右辺が$c$となるので$ax+by=c$は整数解をもつ。${}_\blacksquare$

古典計算機で素数を確率的に判定するアルゴリズム

Shorのアルゴリズムでは、ある数が素数であるかを判定する必要があります（Ref.Hosoya）。素数を決定論的に多項式時間で判定するアルゴリズムは現在まで知られていません。しかし確率的に多項式時間で判定する方法が存在します。以下はRabinRabinによります（Ref.HosoyaP137 E.2より引用）。

素数判定の確率的アルゴリズム（Ref.HosoyaP137 E.2より引用）

$N$より小さい正の整数全体を$A$とする。$N$に依存する「証言関数」$F:A\to\{0,1\}$があり、次の性質をもつとする:

$N$が素数ならば$F(x)=1, \ \ \ \forall a\in A$
$N$が合成数ならば$F(a)=0, \ \ \ \exists a\in A$

素数判定は以下のようにする。$N$より小さい「証言数」$A^w=\{a_1,a_2,\cdots,a_m\}$をランダムにえらび
$$ \hspace{1.5cm}F(a_i)=0, \ \ \ \exists i=1,\cdots,m $$
ならば$N$は合成数。一方
$$ \hspace{1.5cm}F(a_i)=1, \ \ \ \forall i=1,\cdots,m $$
ならば確率
$$ \hspace{1.5cm}1-\frac{1}{4^m} $$
で$N$を素数と判断してよい。

ランダムに選ぶ数$a_i$を増やしていけば、判定を誤る確率はいくらでも小さくなるが、多項式量（$m\simeq \log N$）だけで十分である。

具体的な証言関数は以下のようにして作ります。

証言関数の具体的な構成（Ref.HosoyaP137 E.2より引用）

$N-1=2^kM$のように因数2をくくりだして
$$ \hspace{1.5cm}F(a)=1,\\ \text{if }a^{N-1}=1 \text{ mod }N,\\ \text{and }a^{\frac{N-1}{2^i}}=1 \text { mod }N, \ \ \ \forall i=1,2,\cdots,k $$
そうでないとき
$$\hspace{1.5cm} F(a)=0 $$
と定義する。

以下の定理が知られています：

$N$が素数ならばすべての証言数$a$が$F(a)=1$を証言し、$N$が合成数ならば$3/4$以上の証言数$a$が$F(a)=0$を証言する

これより上の確率的アルゴリズムが成立します。

フェルマーの小定理

$a$を素数$p$の倍数ではない数とする。このとき
$$ a^{p-1}\equiv 1 \ \mathrm{mod} \ p $$
が成立する

以下$\equiv$は$p$での$\text{mod}$で等しいことを表す。

帰納法で示す。$p$と互いに素である正の整数$a$に関して、$a^p\equiv a$なら、両辺$a$でわって$a^{p-1}\equiv 1$となり、フェルマーの小定理が成立する。そこで$a^p\equiv a$を示す。

$a=1$なら$a^p\equiv a$は明らか。
$a=m$のとき命題の成立を仮定する。
$(m+1)^p=m^p+1+\sum_{k=1}^{p-1}{}_p C_k m^k$である。ここで
\begin{align} \hspace{1.5cm} {}_pC_k=\frac{p!}{k!(p-k)!}=\frac{p(p-1)\cdots (p-k+1)}{k!} \end{align}
でありこれは整数だが、$p$は素数なので$k!$では割られず、必ず因数に$p$をもつ。よって
\begin{align} \hspace{1.5cm} (m+1)^p\equiv m^p+1 \end{align}
ゆえに$m^p\equiv m$なら$(m+1)^p\equiv m+1$。