Order finding与大整数分解

初等数论 量子计算

---

0. 背景的背景的背景：符号

从一个集合$S$均匀选取一个元素:$a \leftarrow_R S$
如果$S$有生成元$g$，那么从$S$中均匀抽样的等价描述是：$k \leftarrow \{1,...,|S|\},返回g^k$
群G的阶:群的元素个数$|G|$
元素$a$的阶:$min\{r | a^r = 1_G\}$,$1_G$是$G$的单位元

1. 背景的背景：基本引理

引理0. 充分事件和必要事件的概率
设事件$B$为$A$的必要事件（即$A \rightarrow B$）
则有$Pr\{A\} \le Pr\{B\}$

引理1. 元素阶的最小性
设$g \in G$的阶为$r$，则$\forall t,g^t=1_G$，有$r | t$。

引理2. 素数幂群是循环群
设$p$是一个奇素数,$\alpha$是一个正整数。
则 $\mathbb{Z}^*_{p^\alpha}$是循环群（存在生成元）

引理3. 中国剩余定理
设$m_1,...,m_n$是一系列的正整数并且它们两两互素。
则如下的一系列方程组:
$\begin{equation} x =a_1 (mod \ m_1) \\ x =a_2 (mod \ m_2) \\ ...... \\ x =a_n (mod \ m_n) \end{equation}$
在模$N=m_1 \cdots m_n$下有唯一解。

存在多项式算法求解中国剩余定理中的唯一解。

2. 数论背景知识

定理1. 平方差与大整数分解
设$N$为一个合数，且$x$是$x^2 = 1 (mod \ N)$的非平凡解（即$x \neq 1 且 x \neq -1 (mod \ N)$）
那么$gcd(x-1,N)$和$gcd(x+1,N)$中至少有一个是$N$的非平凡因子。

证明:
$x^2 = 1 (mod \ N)$
$\Rightarrow N | (x^2-1)$
$\Rightarrow gcd(x+1,N) \neq 1$或$gcd(x-1,N) \neq 1$
(这里解释一下第二个推导箭头:因为$N \nmid (x+1)$且$N \nmid (x-1)$。假设$gcd(x+1,N) = 1$且$gcd(x-1,N) = 1$,由这个假设可以推出$N \nmid (x^2-1)$，矛盾。所以$gcd(x+1,N) \neq 1$或$gcd(x-1,N) \neq 1$

另外，如果有满足定理1的$x$,那么找出$N$的一个非平凡因子,即计算$gcd(x-1,N)$和$gcd(x+1,N)$,只需要$O(log(N))$的时间。

定理2. 群$Z^*_{p^\alpha}$中偶数阶元素和奇数阶元素至少各分一半
设$p$为一个奇素数,$\alpha$为一个正整数.
设$d$为使$2^d$满足$2^d| \varphi(p^\alpha)$的最大的值（即$2^{d+1} \nmid (\varphi(p^\alpha)$）
则,阶可被$2^d$整除的元素与阶不可被$2^d$整除的元素个数各分一半。

证明:
因为$\varphi(p^\alpha)$是一个偶数，所以$d \ge 1$。
由引理2，$\mathbb{Z}^*_{p^\alpha}$存在生成元$g:g^{\varphi(p^\alpha)}=1_G$,设$k \in \{1,...,\varphi(p^\alpha)\}$。
设$r$为$g^k$的阶,即$(g^k)^r = 1_G$.由引理1,有$\varphi(p^\alpha)|kr$
若$k$是一个偶数:
$(g^k)^{\varphi(p^\alpha)/2}$
$= (g^{\varphi(p^\alpha)})^{k/2}$
$= 1^{k/2}$
$= 1 (mod \ p^\alpha)$
$\Rightarrow r | \varphi(p^\alpha)/2$
$\Rightarrow 2^d \nmid r$　　　　　　　　（如果$2^d|r$,则$2^{d+1}|\varphi(p^\alpha)$,违反$d$的最大性)

若$k$是一个奇数
$\varphi(p^\alpha) | kr$
$\Rightarrow 2^d | kr$　　　　　　　　　　　　　　　　　　　　　　　（由$2^d | \varphi(p^\alpha)$）
$\Rightarrow 2^d | r$　　　　　　　　　　　　　　　　　　　　　　　　（由$k$为奇数）

由于$k \in \{1,...,\varphi(p^\alpha) \}$（该集合元素个数为$\varphi(p^\alpha)$），而$\varphi(p^\alpha)$是一个偶数，所以阶可被$2^d$整除的元素与阶不可被$2^d$整除的元素个数各分一半。

命题1
$p_j$为素数,$\alpha_j$为正整数，设$x_j \leftarrow_R Z^*_{p^{\alpha_j}_j}$,其阶为$r_j$.
设$d$为使$2^d$满足$2^d| \varphi(p_j^{\alpha_j})$的最大的值（即$2^{d+1} \nmid (\varphi(p^\alpha)$）
如果$r_j | r$且$r$是个偶数，并且有$x^{r/2}_j = -1 (mod \ {p^{\alpha_j}_j})$,则 $2^d|r_j$

该命题在定理3中被使用到.

证明:
由引理2，有生成元$g^{k_j}_j = x_j$.　　$(g^{k_j}_j)^{r_j} = 1 (mod \ p^{\alpha_j}_j)$
$k_j$有两种情况:
case 1: $k_j$为奇数,类似于定理2的证明,有$2^d| r_j$
case 2: $k_j$为偶数
$x^{r/2}_j = -1 (mod \ p^{\alpha_j}_j)$
$\Rightarrow (g^{k_j}_j)^{r/2} = -1 \ne 1 (mod \ p^{\alpha_j}_j)$
$\Rightarrow \varphi(p^{\alpha_j}_j) \nmid \frac{rk_j}{2} = r \cdot \frac{k_j}{2}$
又由$r_j | \varphi(p^{\alpha_j}_j) ，有r_j \nmid r \cdot \frac{k_j}{2}$
但由有$r_j | r$应有$r_j | r \cdot \frac{k_j}{2}$
出现矛盾，即$k_j$不会是偶数，即有$2^d| r_j$

定理3. 偶数阶元素大概率是非平凡因子
设$N = p^{\alpha_1}_1\cdots p^{\alpha_m}_m$（整数素因子分解）且$N$为一个奇合数。
设$x \leftarrow_R \mathbb{Z}^*_N$，$r$是$x$的阶（$mod \ N$）。
则有

$$Pr\{ \text{ $r$是偶数且$x^{r/2} \ne -1 (mod \ N)$} \} \ge 1 - \frac{1}{2^m}$$

证明:
即证

$$Pr\{ \text{ $r$是奇数 或 $r$是偶数且$x^{r/2} = -1 (mod \ N)$} \} \le \frac{1}{2^m}$$

由中国剩余定理，从$\mathbb{Z}^*_N$均匀抽样出一个$x$等价于:依次从$\mathbb{Z}^*_{p^{\alpha_j}_j}$均匀抽独立样出$x_j$(j = 1,...,m)，用中国剩余定理对应的算法求出$x(x \equiv x_j (mod \ {p^{\alpha_j}_j}), j=1,...,m)$。

对于任意的$j$(注意$j$的任意性!),设$r_j$为$x$在$\mathbb{Z}^*_{p^{\alpha_j}_j}$上的阶，当然它也是$x_j$在该群上的阶。由于$p^{\alpha_j}_j | N | (x^r-1)$，所以有$x^r \equiv 1 (mod \ p^{\alpha_j}_j)$，即有$r_j | r$。
$r_j$有两种情况:

case 1:当$r$是一个偶数且$x^{r/2} = -1 (mod \ N)$:
$x^{r/2} = -1 (mod \ N)$
设$d$为使$2^d$满足$2^d| \varphi(p_j^{\alpha_j})$的最大的值（即$2^{d+1} \nmid (\varphi(p^\alpha)$）
使用命题1,有$2^d|r_j$,在$x_j$是均匀抽取的情况下，该发生概率为$\frac{1}{2}$

case 2:当$r$是一个奇数:
$2^{d_j} | r_j | r$
　$\Rightarrow$ $r_j$是一个奇数.由定理2,在$x_j$均匀抽取的情况下,该情况发生的概率为$\frac{1}{2}$
　
综合以上两个case,由$j$的任意性与各$x_j$的独立性和引理0：有

$$Pr\{ \text{ $r$是奇数 或 $r$是偶数且$x^{r/2} = -1 (mod \ N)$} \} \le \frac{1}{2^m}$$

Note:看不懂证明没关系，记住每个定理的描述。

3. Order finding 与 Factoring

(以下全设$N$为奇合数)
Factoring:给定正整数$N$,求$N$的素因子分解。
Order inding:给定$Z^*_N$中的一个元素$a$，求解$a$的order.

为什么Order finding与Factoring会有关系？因为如果可以多项式时间内求解Order finding问题，则可以带概率地在多项式时间内求解Factoring。

Factoring问题可规约为整数拆分问题:
整数拆分:求解$N_1,N_2 < N$使得$N = N_1 \cdot N_2$

Factoring问题可以规约为$O(\log{N})$个整数拆分问题。(为什么渐进界是$\log{N}$？请简单思考一下)而且该规约是确定性规约：即存在确定性多项式时间算法求解整数拆分，则存在确定性多项式时间算法求解Factoring。

而根据上面的一系列数论背景，如果我们能高效地求解order finding,那么我们可以以一个大的概率（参考定理3）求解整数拆分问题。所以在这里，Factoring的关键是求解Order finding。综合前面面描述的定理，可以得到以下求解整数拆分问题算法的一个高层次描述（素因子分解算法的描述简单，略）：

输入:大整数$N$
输出:对$N$的拆分
1. 判断$N$是否是一个素数power$(N = p^\alpha,p为素数)$,如果是使用相应算法返回$p$
2. $x \leftarrow_R \mathbb{Z}_N$.如果$gcd(N,x) > 1$，返回相应的拆分
3. 使用order finding算法求解$x$的order $r$
4. 如果$r$为偶数，则判断$gcd(N,x^{r/2}-1)和gcd(N,x^{r/2}+1)$哪个是$N$的非平凡因子并返回。否则，算法失败。

由定理三，以上算法失败的概率大于等于50%。

求解大整数分解量子算法唯一的量子部分就在于Order finding。其它的整数拆分等步骤都是经典算法。而之所以大整数分解在量子模型下存在高效算法是因为存在求解Order finding的多项式时间量子算法。