文档介绍：: .
Shor算法原理
摘要：以数学家彼得？秀尔命名的Shor算法(秀尔算法)，于1994年 发现，是一个针对整数分解的题目的量子算法 (在量子计算机上面运 作的算法)。比较不正式的说，它解决题目如下：给定一个整数 N, 找出他的质因子。
关键词：shor算法；RSA密码体系；量子傅立叶变换
0引言
Shor算法非常重要，因为它代表使用量子计算机的话，可以用来破解已被广 泛使用的公开密钥加密方法，即 RSA加密算法。RSA算法的基础在于假设了我们 不能很有效率的分解一个已知的整数。 就目前所知，这假设对传统的(也就是非 量子)电脑为真；没有已知传统的算法可以在多项式时间内解决这个问题。 然而,
Shor算法展示了因子分解这问题在量子计算机上可以很有效率的解决，所以一 个足够大的量子计算机可以破解 RSA
1 RSA公钥密码体系安全性
公钥密码系统的安全性主要取决于构造算法所依赖的数学问题， 它要求加密函
数具有单向性(即求逆的困难性)，因而密码分析者要从公开密钥得到秘密密钥对 于目前的计算能力来说是不可行的 ⑴。RS/密码体系的基本原理是：
(1) 找到两个大质数p和q(作素性检查)，并计算n = p q「(n) =( p - 1)(q -1)。
随机选择一个小于：:(n)但与「(n)互质的整数。计算「(n)模运算的逆无
d = 4 mod「(n)
宣布公开钥为(n/ )，私钥为(p，q)或do
(2) 选取公开钥(e，n)，满足条件gcd( (n),e) =1
(3 )加密：寻找满足条件的 do
de =| mod '(n) | d与e为模mod (n)运算下互逆的。
将平文编码 me=ymod(n)
(4)解密：y= m。
2 Shor算法
：
设N为要分解的大整数,选择m使之满足B二am/2-1, N2 ：：： 2m ：：： 2N2。
a. 随机地选择一个与N互质且小于N的自然数。
求函数f(x)二zamodN a =0,1,2,3,…的周期T。显然f(x)所取的值属于正整数集 合{1,2…,N-l},而且是一个周期性的函数［2］。
b. 求n的因子
gcd(卩=1, n) • — . zT = ( p,q)
Shor算法最关键之处是利用量子傅立叶变换求f(x)的周期，所以只要求得f (x) 的周期，就可以对N进行分解。
测量法
在Shor算法中，函数f(x)周期的信息是通过量子傅立叶变换 QFT(Quantum
Fourier transformation) 来提取的⑻。
首先，我们对两组有m个量子比特的存储器进行幺正变换得到纠缠状态：
2m J
E | xi| f (xj)，式中 f (x) = za mod N。
r =0
对存储器X进行傅立叶变换：
2m 4
旳=2皿2送尹/2" k)
k=0
可以看出，量子QFT就是将态前面的叠加系数变为原叠加系数的离散傅立叶变 换，并且可以证明，上述变换大约可以在 m步骤内完成⑷。
由于f(x)的周期，式(4)中许多项可以合并，相消或