第四周将学习shor算法
官方笔记我放在最后
前言
本章全是数学推导, 所以本文会没什么内容, 官方笔记已经很详细了
对于RSA算法部分, 看wiki的RSA加密算法理解起来更快
官方在讲量子傅里叶(Quantum Fourier transform)变换时, 课件以及pdf笔记中的QFT是反的, 所以原来的x0会变成y2, wiki的Quantum Fourier transform是正的, x0变换后是y0, 最后的shor算法例子中的QFT也是正的官方笔记错误
公式(8)下面文字下的那一行公式左边e的指数少了一个负号(下文图片中我已修复)
个人思考
在公式(22)下面证明r的唯一性那个地方我感觉有点不太对, 有公式(20)可知good y与k是一一对应的, 若存在不同的r, 式子应写成$$\left| \frac{k}{r_1} - \frac{k}{r_2}\right| = \frac{k|r_2-r_1|}{r_1 * r_2} \geq \frac{1}{r_1 * r_2} = \frac{1}{N}$$从而证明了r的唯一性
对于官方笔记的证明方法, 如果$a = 3, r_1=10, b=6, r_2=20$不就为0了?
第三页证明
关于第三页, 我用自己的话重新讲一遍证明过程, 官方笔记和课件感觉有点难理解
官方笔记第三页对a的概率证明应该是本章最难的东西了
数学知识预备
Multiplicative order
比如对于下面这句话的理解(第三页第三行)
$r_1$ and $r_2$ are the orders of $a_1$ and $a_2$ in the rings $\mathbb{Z_p}$ and $\mathbb{Z_q}$.
即, 使$a_1^{r} \equiv 1 (mod\ n)$成立的最小的正整数为$r_1$, r2同理
Fermat’s little theorem
看上面链接公式就可以理解第三页倒数第二行中间的话了(The order of b is $2^{k_p}s_p$)
Primitive root modulo n
比如对于下面这句话的理解(第三页倒数第三行)
Let $b$ be the primitive element of the field $\mathbb{Z_p}$
即当$b^{m_p}$中的${m_p}$从1到$p-1$取一遍时, 那么$b^{m_p}(mod\ p)$的值也从1到$p-1$取一遍, 顺序会乱(想要直观一点可以直接看上面wiki链接里的例子)
问题描述
当我们随机取一个a时, 满足下列条件(3)(4)的概率是多少?
$$r = 0(2) \tag{3}$$
$$(a^{r/2}+1)\neq0(N) \tag{4}$$
过程
下面证明中用$(p)$表示$(mod\ p)$, $r\mid s$表示s能整除r
现在我们已经随机选择了a
已知
r is the order of the element a in the ring $\mathbb{Z_n}$
$$a^r = 1(N)\tag{1}$$
$$N=pq$$
开始求概率
$$a_1 = a(p)\tag{2}$$
$$a_2 = a(q)$$
$r_1$ and $r_2$ are the orders of $a_1$ and $a_2$ in the rings $\mathbb{Z_p}$ and $\mathbb{Z_q}$.
即
$$a_1^{r_1}(p) = 1\tag{3x}$$
$$a_2^{r_2}(q) = 1$$
由(1)可知, $a^r(p) = 1$
由(2)可知, $a = pk_1 + a_1$, 将其带入上一行的式子
$$(pk_1+a_1)^r(p) = 1 \Longrightarrow a_1^r(p) = 1$$
又因为$r_1$和$r_2$是order, 故r是$r_1$的倍数, 同理r是$r_2$的倍数
构造$s = kr_1r_2$
$$a^s(p) = (pk_1 + a_1)^s(p) = a_1^{kr_1r_2}(p) = (a^{r_1})^{kr_2}(p)$$
又因为(3x)
所以$a^s(p) = 1$, 等价于
$$a^s = pk_1+1 \tag{5}$$
同理
$$a^s = qk_2+1 \tag{6}$$
(5)(6)左边相等, 所以右边相等, 即
$$pk_1 = qk_2 \tag{7}$$
p,q 互质, 所以k1一定是q的倍数
将(5)改写为
$$a^s = pq\frac{k_1}{q} + 1 \Longrightarrow a^s = 1(pq) \Longrightarrow r\mid s$$
即对于任意s都能整除r, 又因为s和r都是$r_1$和$r_2$的倍数, 且对任意s成立, 所以
$$r = LCM(r_1, r_2)$$
我们接下来把$r_1$和$r_2$进行分解(把里面的2提出来, 比如$5 = 2^05$, $28 = 2^27$)
$$r_1 = 2^{c_1}odd_1, c_1\geq0 \tag{8}$$
$$r_2 = 2^{c_2}odd_2, c_2\geq0 \tag{9}$$
如果$c_1 \neq c_2$(比如$c_1 > c_2$), 则同时满足了(3)(4)
$$r = 2r_2int$$
$$a^{r/2}=a^{r_2int}=1(q) \Longrightarrow a^{r/2}\neq-1(q) \Longrightarrow a^{r/2}\neq-1(pq)$$
$c_1$和$c_2$取决与a, 下面让我们来计算$c_1 \neq c_2$的概率
首先将p用另外一种形式表达
$$p=2^{k_p}s_p+1,\ \ s_p=1(2)$$
令$b$ be the primitive element of the field $\mathbb{Z_p}$, 由上面的Primitive root modulo n知, 可将$a_1$用另外一种方法表示出来
$$a_1 = b^{m_p}(p),\ \ m_p \in {1,\cdots,2^{k_p}s_p}$$
将上面这个式子带入(3x)
$$b^{m_pr_1} = 1(p)$$
由费马小定理可知
$$b^{p-1} \equiv 1(p) \Longrightarrow b^{2^{k_p}s_p} \equiv 1(p)$$
再根据Primitive root modulo n可知$2^{k_p}s_p$是order(因为只有当指数为p-1时才为1, 其余时为其他数字, 而p-1就是最小的正整数, 即为order)
故$m_pr_1 = 0(2^{k_p}s_p)$
同理可得$m_qr_2 = 0(2^{k_q}s_q)$
$$\begin{cases}
m_pr_1 = k_12^{k_p}s_p\\
m_qr_2 = k_22^{k_q}s_q\\
\end{cases}
$$
回忆一下, 我们只是想知道(8)(9)中含有不同的2个数的概率
最糟糕的情况, 也就是$r_1$和$r_2$有相同2个数的概率最大时候, 此时右边$k_1 = k_2 = k_q = k_p = 1$, 即右边只有一个2, 如果右边有很多个2, 那么$r_1$和$r_2$有相同2个数的概率会非常小
在最糟糕的情况下, $r_1$和$r_2$都分到2和$r_1$和$r_2$都没分到时$c_1$和$c_2$相等, $m_p$和$r_2$分到或$m_q$和$r_1$分到时$c_1$和$c_2$不相等
最糟糕的情况下概率为1/2
为什么$k_p$或$k_q$不能为0?
如果为0, 即p或q为2, 不用量子计算机也能快速分解, 所以$k_p \geq 1$, $k_q \geq 1$
官方笔记
