更多安全资讯和分析文章请关注启明星辰ADLab微信公众号及官方网站（adlab.venustech.com.cn）
为了更通俗易懂，本文涉及的公式推导都尽量详细，力求高中水平就能看懂，你既不需要懂密码学，也不需要懂量子力学也能明白算法的精髓。本文将详细分析Shor算法的实现过程，整数周期数及非整数周期数下Shor算法分析，Shor算法概率评估，实例分析。不得不说，量子计算以及量子计算机是一个很庞大的知识体系，个人水平有限，此处我们仅仅就单纯地围绕Shor算法本身进行探讨分析，不考虑退相干对算法的影响，也不考虑物理实现。
一个量子可以同时处于两种状态的叠加（比如自旋向上和自旋向下），这种叠加态测量的瞬间就会随机变为一个确定的态（测量得到自旋向上），这个过程叫波函数的坍塌。我们如果将这两个态表示为0,1，而每种态观测后出现的概率幅(注意不是概率，概率幅的平方为概率)为,那么这个量子可以表示为：
这里叫狄拉克符号，表示量子态，为基态，+表示叠加，两种态的概率幅平方和为1，即。而我们通常说的量子计算就是通过量子逻辑门来操作处于叠加态的量子。比如Hadamard门，简称H门（在量子计算中非常重要），他的一个主要功能就是通过计算基态产生等概率的叠加态。通过H门变换后的单量子叠加态为：
两种基态的坍塌概率都为 ，两个量子的H门得到的结果如下：
每个态坍塌的概率 ，对于n个量子的H门变换后：
其他量子门这里就不做介绍了，本文暂时不会涉及，想更深入了解可以到维基上看。
https://en.wikipedia.org/wiki/Quantum_logic_gate
量子门及其对应的门矩阵如下图：
还有一个比较重要的复合门是受控U(a,x)门，想深入了解的看这篇文章：一只冰牙喵：4.2 受控操作。
不过这里看不懂没关系，我们只需要知道受控U门可以用于计算以a为基底的幂，其一般用于生成指数函数值。
量子并行运算（Quantum Parallelism）是基于量子叠加态（Quantum Superposition）和幺正变换实现的。量子计算正是有了数据的可叠加性和幺正变换，从而决定了一次操作即可改变全部数据。比如有量子寄存器，存了10个处于叠加态的量子，在通过运算时只需要一次性操作这10个量子，但是由于可叠加性，这10个量子叠加态可以表示2^10个基矢，一次操作10个量子，相当于一次对2^10个基矢进行了操作，这就大大提高了运算的速度。
在经典计算中，并行性的核心思想是将一个计算任务分配给多个处理器同时运行，要快于使用一个处理器来运行。在理想的情况下，将工作分配给K 个处理器就应该使计算时间缩短为原来的1/K。但是现实肯定不是这样的，真实的任务往往具有串联性，只有部分具有并联性的子任务才能够做并行运算。由于量子计算的特点是数据的可叠加性质和操作的幺正变换本质，从而就决定了量子计算的语义特征是完全意义上的通过一次操作即可改变全部数据的并行计算。将一个N 位量子寄存器中的 个数据同时通过一次幺正变换（即进行一次运算）所需的时间定义为 ，而经典计算中对一个数据进行运算的时间为 ，因为一次量子计算就对所有的数据做了并行处理，所以量子计算加速能力可以表示为
如果 ,那么加速能力 ,也就是说对量子计算机做一次运算，相当于对经典计算机做 次运算。
量子计算机是严重依赖于优秀的量子算法的实现，虽然通用量子计算机能做经典计算机的所有事情，但是只有在处理特定问题上量子计算才具有决定性的优势，目前已经有很多优秀的量子算法，其中对大数因子分解，离散对数问题以及更一般的隐含子群问题的解决有着开创性和重大影响的量子算法便是本文要详细分析的Shor算法。
本文将非常详细的分析Shor算法来让各位明白量子计算在解决特定问题上的巨大优势。
二、Shor算法分析
在费曼提出量子计算机概念不到15年的时间，shor通过研究出的量子算法给世人了一剂强心针，自从shor算法出来后，人类开始加速了量子计算机的研制，各大头部企业也纷纷加入了量子计算机的量子竞赛行列。
shor算法最令人振奋的是直接将质因子分解以及离散对数问题以指数级速度提升，这给人们的启示是可以利用同样算法思想来解决更为广泛的隐含子群问题。
我们知道RSA是基于经典计算机大数质因式分解的指数复杂度的困难而设计的一种非对称加密算法，目前最优的因子分解算法为指数复杂度 。而通过shor量子算法可以以多项式复杂度完成大数因式分解，从而可以快速破解RSA算法。那么Shor算法是如何发挥如此威力的，简单来说，Shor算法的核心依赖于三个变换即H变换,U变换,QFT(量子傅立叶)，接下来我们一步一步的分析。
Shor算法量子实现线路简图：
我们设RSA的公钥为 (e,N) ，私钥为 (d,N) ,那么生成公私钥的过程如下：
首先我们需要将大数因子分解问题转化为以求待分解的合数N为模的函数 的周期问题。
设周期函数 的周期为r（这里a为小于N，且与N互质的整数），则有：f(x)=f(x+r) , 那么：
设整数 ，则
例如：设 N=15，a=7 ,则：
设量子比特长度为 L, 则总共可以表示的 个基态, 设N为要分解的合数，为了确保 长度内有足够的周期数，我们需要满足
两个寄存器展开形式如下：
由于 f(x) 为周期函数，设周期为r，A为总长中存在的周期数，则
设l为小于一个周期内的x的值, x=l+Ar, 则整个系统的态实际为：
因此，x可以表示为
然后对reg2进行计算基上的测量，设测量结果设为 Z ，测量Z在reg1中的投影变化为：
经过投影后
上式可以变换为：
A.整数周期
在(2)式的[ ]中，在 的整数倍情况下变成，出现相长干涉，求和后为 ，如果不为整数，则为相消干涉，其值趋于0. 所以
当 时，我们通过等比数列转化得到：
带入（0）式得：
由于 ，也就是说，当 ，也即不为整数，则为相消干涉，其值为0。
通过量子傅里叶变换后得到如下叠加态
测量 的值， 等概率 地选择出一个态。由 得：
如果有 , r 就可以从 的不可约分数求出。
B. 非整数周期
不能整除 r 的情况下,那么在x值范围内的周期数A便不是整数，此时我们加入微调参数 稍作调整，使得 为整数，设
因此(2)式的[ ]为：
这里 的值极小，该值用于逼近函数的峰值，我们再令
因此(3)式的平方表示为
由于
因此
所以得到 的概率为
这里，为了严谨讨论，我们设 小于等于1/2（如果大于1/2，可以认为是下一个整数 ，所以这是适用于所有情况的
由(4)(5)得：
当
必位于原点与点 连线的上方，所以
而对于任意 为凸函数，有：
又因 ,因此：
所以，测量 的概率为
最后，我们来讨论测量值 ,有
所以
这里 已测得，这里严格存在一个分数 ,可由 的连分数展开求出（下一个节将通过实例说明），通过约分满足 就可得到 r 的值，gcd算法的成功率为
三、实例分析
虽然上面已经分析得很透彻了，但是估计还是有人觉得会太抽象，所以下面我以一个例子来进行实例分析，以帮助理解。
对于 ，N=91，a=4，那么
f(1)=4,f(2)=16,f(3)=64,f(4)=74,f(5)=23,f(6)=1
所以周期为 r=6， ,，然后根据2，3式我们计算得到：
这里， 是我们测量得到值，如果这个值为0，那么对于我们求周期r是没有意义的，所以除开这种情况下，测得其他值的概率和为0.623。如果测量的值为13653，那么我们来计算0.833312的连分数。
1/0.833312=1.200031,
1/0.200031=4.999225,
1/0.999225=1.000775,
1/0.000775=1290.322580
这里遇到大数1290，我们就终止，最后我们得到连分数为
那么我们就可以确定 k=5,r=6 了吗，那有没可能 k=10,r=12 呢，所以，我们不能单纯的通过一次测量来确定周期，我们来考察其他几项，我这里不再一一去展开了，懒人可以在这里去计算(连分数计算 -连分数计算器-分数计算器)。
因此，如果我们将shor算法多执行几次，最后求出各个分母的最小公倍数，那么这个最小公倍数就是我们要找的周期r，有了周期r，我们就不难求出合数N的质数因子了，进而也能够比较容易破解RSA算法了。
四、离散对数问题简析（不感兴趣可以略过，有时间补充）
通过对shor算法原理的剖析，我们可以知道，对于任何具备转化为求周期函数的周期为目标的问题都可以用同样算法以指数加速来快速解决，比如离散对数(ElGamal), ECC之类的非对称加密算法都可以用同样的思想来解决。
离散对数多说两句，Shor在其原始论文中对于素域上的离散对数问题，给出了一个基于整数求阶量子计算算法求解算法,成功率为1/480。Shor指出在解决素域上的离散对数问题时，其实并没有利用到素域的特性，因而对有限域上的离散对数问题也同样成立。后来Eicher和Opku给出了一个在多 项式时间内以1/480的成功率攻击椭圆曲线离散对数问题的量子计算算法。
设一个阶为 p ,且生成器 为g 的群,如果,那么对于部分 ,我们希望得到 r ,那么 r 就是离散对数 .
比如EIGamal加密，对于随机大大素数P,以及随机数x,满足
这里 (y,g,P) 为公钥， x 为私钥。我们将长度为我们将长度为 的消息分组为
那么计算密文
这里c1,c2为加密后的密文,那么解密过程如下：
简单推一下
考虑abelian 群(每一个因子对应于值的模加)。那么函数
这给我们呈现了一个abelian 隐含子群问题，同时可以看出映射 f 是一个群同态。kernel为 (r,1) 的倍数，所以如果我们能找到kernel，我们就能够找 r。
对于函数,设周期为 和 ，那么
因此，我们只要通过量子算法求得周期 就可以得到 r 。使用量子算法处理离散子群问题，和我们前面讲解的方法非常类似，后续有时间再分析吧。
参考文章：
Shor, P.W. (1994). “Algorithms for quantum computation: discrete logarithms and factoring”. Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134
https://authors.library.caltech.edu/2179/1/BECpra96.pdf
https://en.wikipedia.org/wiki/Quantum_logic_gate
https://en.wikipedia.org/wiki/Shor%27s_algorithm
https://en.wikipedia.org/wiki/Discrete_logarithm
https://zhuanlan.zhihu.com/p/106923175
启明星辰积极防御实验室（ADLab）
ADLab成立于1999年，是中国安全行业最早成立的攻防技术研究实验室之一，微软MAPP计划核心成员，“黑雀攻击”概念首推者。截止目前，ADLab已通过CVE累计发布安全漏洞近1100个，通过 CNVD/CNNVD累计发布安全漏洞2000余个，持续保持国际网络安全领域一流水准。实验室研究方向涵盖操作系统与应用系统安全研究、移动智能终端安全研究、物联网智能设备安全研究、Web安全研究、工控系统安全研究、云安全研究。研究成果应用于产品核心技术研究、国家重点科技项目攻关、专业安全服务等。
原文始发于微信公众号（ADLab）：Shor量子算法推演与分析
