Sho算法原理.docVIP

Shor算法原理 摘要：以数学家彼得?秀尔命名的Shor算法（秀尔算法），于1994年发现，是一个针对整数分解的题目的量子算法（在量子计算机上面运作的算法）。比较不正式的说，它解决题目如下：给定一个整数N，找出他的质因子。 关键词：shor算法；RSA密码体系；量子傅立叶变换 0 引言 Shor算法非常重要，因为它代表使用量子计算机的话，可以用来破解已被广泛使用的公开密钥加密方法，即RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知，这假设对传统的（也就是非量子）电脑为真；没有已知传统的算法可以在多项式时间内解决这个问题。然而，Shor算法展示了因子分解这问题在量子计算机上可以很有效率的解决，所以一个足够大的量子计算机可以破解RSA。 1 RSA 公钥密码体系安全性 公钥密码系统的安全性主要取决于构造算法所依赖的数学问题，它要求加密函数具有单向性(即求逆的困难性)，因而密码分析者要从公开密钥得到秘密密钥对于目前的计算能力来说是不可行的[1]。RSA密码体系的基本原理是： (1)找到两个大质数p 和q(作素性检查)，并计算。 随机选择一个小于但与互质的整数。计算模运算的逆无 宣布公开钥为，私钥为(p，q)或d。 （2）选取公开钥（e，n），满足条件 （3）加密：寻找满足条件的d。 d与e为模运算下互逆的。 将平文编码 （4）解密：。 2 Shor算法 2.1 因数分解： 设N为要分解的大整数,选择m 使之满足。 a.随机地选择一个与N互质且小于N的自然数。 求函数 的周期T。显然f(x)所取的值属于正整数集合{1,2…,N-l},而且是一个周期性的函数[2]。 b.求n的因子 Shor 算法最关键之处是利用量子傅立叶变换求f(x) 的周期，所以只要求得f (x)的周期，就可以对N进行分解。 2.2 量子傅立叶变换 2.2.1 测量法 在Shor 算法中，函数f(x)周期的信息是通过量子傅立叶变换QFT(Quantum Fourier transformation)来提取的[3]。 首先，我们对两组有m 个量子比特的存储器进行幺正变换得到纠缠状态： ，式中。 对存储器x进行傅立叶变换： 可以看出，量子QFT就是将态前面的叠加系数变为原叠加系数的离散傅立叶变换，并且可以证明，上述变换大约可以在m2步骤内完成[4]。 由于f(x) 的周期，式(4) 中许多项可以合并，相消或近似相消，最后得出只有k取下列各值时系数(概率幅)明显不为0[4]: 式中括号表示取大于它的最小整数，因此除了k=O外有: 我们可以对k存储器进行测量，可以测到k的本征值，当我们测到这些值后，再通过式上式计算出f(x) 的周期T。 得到f（x）的周期后，按照普通算法，可以推导出N的因子。 2.2.2 理论推导 1) 将两个寄存器R1和R2初始化为0,即。 2) 对R1中的每一位作H变换其中H为哈德曼门： 式中，，（其中m限制条件为：QFT可由两种量子门实现,所用的门 的数量为m(m+1)/2），可以看出R1保存了从0到q-1的所有的数的叠加。 3)对做幺正变换，变换结果存入R2。 此时，R1和R2处于纠缠态。 4）测，假定其态坍缩为。因为的周期为T，所以有，其中，是小于的最大整数，故： 坍缩时，相对应地坍缩为： 可得，是以T为周期的一组态的叠加。若q是T的整数倍，设，则有： 其中： 5）对作QFT： 其中： 所以： QFT使所需结果增强，并且使不需要的结果为0。 6）测量，得到，故。因和均已知，若，则可求出T。最大的T即为所求f（x）的周期。 3 举例 以15为例，实现Shor算法的量子逻辑门组合： 4 Shor算法的有效性 Shor算法并不能保证每次运行都能得到正确的结果，当计算成功给一个数，可以除N，即能验证得到的结果是不是N的因子。假设成功的概率是，我们通过重复k次实验，则至少成功一次的概率是。我们可以看出，可以通过增加实验的次数来增加实验成功的概率。所以，Shor算法是一种随机算法。 5 总结 目前，Shor算法已经极大地推进了量子计算机的发展，也促进了物理上实现量子计算机的现实化。 量子算法和量子计算机的发展对于经济、军队等有着重大的意义。量子计算及其密码体系已经改变了目前对计算机的认识，同时，量子计算已经迅速发展成一个新的研究领域，在将来可以为我们提供更多有价值的进展。 参考文献 [1]叶柳. 量子通信中若干问题的研究. 合肥：中国科技大学，2003：35-37 [2]苏晓琴，郭光灿. 量子通信与量子计算. 量子电子学报，2004,21，（6）：713-714 [3]Wade Trappe，Lawrence C.Washington,邹红霞，许鹏文，李勇奇译，密码学概论，北京：人民邮电出