具有高概率的整数分解量子算法
付向群,鲍皖苏,周 淳,钟普查
(解放军信息工程大学电子技术学院,河南郑州 450004)
摘 要: 本文基于量子Fourier变换给出了一个新的整数分解量子算法,通过利用多次量子 Fourier变换和变量
代换,使得 r变成相位因子(r是从模N整数环中所选元素的阶),进而可使非零的非目标态的几率幅变为零,算法成
功的概率大于3/4,高于Shor整数分解量子算法,且不再依赖于 r的大小(Shor算法成功的概率依赖于 r的大小),同时
还将新算法的资源消耗情况与Shor算法进行了对比.
关键词: 量子算法;整数分解;公钥密码;量子Fourier变换
中图分类号: TN3016 文献标识码: A 文章编号: 03722112(2011)01003505
QuantumAlgorithmforPrimeFactorizationwithHighProbability
FUXiangqun,BAOWansu,ZHOUChun,ZHONGPucha
(InstituteofElectronicTechnology,thePLAInformationEngineeringUniversity,Zhengzhou,Henan450004,China)
Abstract: Inthispaper,basedonthequantumFouriertransform,wegiveanewquantumalgorithmforprimefactorization.
ThealgorithmturnsrtobephasefactorunderrepeatedapplicationofFouriertransformandvariatetransform,whereristheorder
ofaselectiveelementintheringofintegersmoduloN.Furthermoretheamplitudeofthenontargetstatesexceptzerostateismodi
fiedtobe0.Ouralgorithm′ssuccessprobability,whichismorethan3/4andhigherthanShor′salgorithm,doesn′tdependonthe
sizeofrotherthanShor′salgorithm.Meanwhile,wepresentacomparisonoftherequiredresourcebetweenthenewalgorithmand
Shor′salgorithm.
Keywords: quantumalgorithm;primefactorization;publickeycrypto;quantumFouriertransform
1 引言
众所周知,量子计算机具有强大的并行计算能力,
以 n比特输入为例,量子计算机可以通过一步运算完
成对2n个输入的计算,
1
2槡 n∑
2n-1
x=0
x,0n〉
U
→
f 1
2槡 n∑
2n-1
x=0
x,f(x)〉
但是在输出运算结果时,每个结果都是等概率地输出.
量子计算算法的作用就是使得想要的结果能以很高的
概率输出.因此按照量子计算机的基本原理,针对需要
解决的实际问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
,设计符合量子计算机运算机理的量子
计算算法是量子计算机解决问题的关键.
在20世纪90年代,出现了两个著名的量子计算算
法:1994年,PWShor[1]提出了一个在多项式时间内求
解整数分解问题和有限域上离散对数问题的量子计算
算法,它在密码学上的重要意义是:利用该算法可以有
效破译,即在多项式时间内成功破译 RSA公钥密码体
制、ECC公钥密码体制和 DiffieHellman密钥分配协议;
1996年,LKGrover[2]提出了一个针对未加整理的数据
库的量子搜索算法,它在密码学上的重要意义是:利用
该算法对密码进行密钥穷尽攻击,计算复杂度可以得到
开平方根的降低.上述两个量子算法的相继提出对现代
密码的安全性带来了巨大冲击,特别是对公钥密码的安
全性产生了巨大影响.因为目前实用的公钥密码体制的
安全性基础大多是基于大整数分解问题或离散对数求
解问题的难解性,而且一些数字签名、秘密共享[3,4]的
安全性也是基于这些问题的难解性.目前,解决大整数
分解问题的最优算法是数域筛法[5],但其计算复杂性是
亚指数时间,即
O e1.923+o(1( )) ln( )N
1/3 lnln( )N 2/( )3 ,
尽管后来一些学者对整数分解问题进行了研究[6],但算
法并不具有普适性.
量子计算下可以有效地求解两个素数乘积的整数
分解问题的核心是 Shor整数求阶量子算法的提出,该
算法是一个概率算法,算法运行一次成功的概率是
4φ(r)/π
2r(φ是欧拉函数,r是ZN中所选元素的阶).
收稿日期:20090504;修回日期:20091222
第1期
2011年1月
电 子 学 报
ACTAELECTRONICASINICA
Vol.39 No.1
Jan. 2011
长期以来,如何进一步提高整数求阶量子算法的成功
概率一直是整数分解问题量子算法研究的难点.D
McAnally[7]在2002年提出一种新的整数求阶算法,该算
法执行两次 Shor整数求阶量子算法得到 ZN中所选元
素阶的概率大于60%,执行四次 Shor整数求阶量子算
法,得到所选元素阶的概率大于90%,但是该算法本质
上仍依赖于 Shor整数求阶量子算法的成功率.本文给
出了一个新的整数分解量子算法,利用量子 Fourier变
换能够将一些输入状态之间的关系变成相位因子这一
性质,通过利用多次量子 Fourier变换和变量代换,使得
0〉态之外的非目标态(对整数分解不起作用的量子
态)的几率幅变为零,算法成功的概率高于 Shor整数分
解量子算法,且不再依赖于 ZN中所选元素阶r的大小,
同时还将新算法的性能与 Shor算法进行了对比.
2 预备知识
为讨论方便,我们约定整数环 ZN= 0,1,…,N{ }-1,
ZN为整数环 ZN中除去零元素的集合,ωn=e2πi/n是 n次
单位根.
求两个整数的最大公因子算法是公元前三世纪由
Euclidean发现的,Euclidean算法[8]主要是利用带余除法
的相关性质求两个数的最大公因子.如果两个整数都
可以
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示为至多 L比特的比特串,那么算法的计算复
杂性是 O(L3).
在经典计算机上求解整数的一个因子问题事实上
等价于整数求阶问题[9].
定义1[10](a模N的阶) 在整数环 ZN中,对于任
意一个 a∈ZN,如果 r是最小的非零整数使得 ar=
1modN成立,那么 r称为a模N的阶.
定义2[10] 对于一个整数 N,x是一个整数满足0
<x≤N和xN,如果 x是1或 N,那么 x称为N的一
个平凡因子,否则称为非平凡因子.
引理1[9] 对于一个整数 N=pt11…ptmm,如果 ZN中
的一个元素x模N的阶r是偶数且xr/2≠-1modN,那么
gcd(xr/2+1,N)或者 gcdxr/2-1,( )N 是N的一个非平
凡因子.
引理2[9] 设 N=pt11…ptmm是正奇合数的素因子分
解,从 ZN中随机选取整数x,x模N的阶为r,则
pr为偶数且xr/2≠-1mod( )N ≥1-12m
由引理1和引理2容易得到推论1成立.
推论1 对于一个整数 N=pq,从 ZN中随机选取
一个与N互素的整数x,x模N的阶为r,那么利用整数
x可以对N进行整数分解的概率为p≥3/4.
定义3(量子Fourier变换)[9] 如果在一组
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
正
交基 0〉,1〉,…,N-1〉上的一个线性算子在基态上
的作用 UF为
UF:j〉|
1
槡N∑
N-1
k=0
ωjkN |k〉
那么对任意的状态的作用可以表示为
UF:∑
N-1
j=0
xj|j〉 |
1
槡N∑
N-1
k=0
∑
N-1
j=0
xjωjkN |k〉
称 UF为量子 Fourier变换.其中,“|”表示为该变换是
可逆变换.
3 Shor整数分解量子算法
1994年,Shor在其原始论文[1]中首次提出了整数求
阶量子算法,并注意到整数因子分解问题可归约为整
数求阶问题,其整数求阶量子算法[1]具体步骤如下:
Step1 给定一个整数 N,L=「logN?,选择两个整
数 m、α,其中 N是两个素数的乘积,N2≤2m≤2N2,1<
α<N-1;
Step2 给定两个 m维量子寄存器,其初态均为
|0m〉,对第一个寄存器做在标准正交基|0〉,|1〉,…,
|2m-1〉上的量子Fourier变换 UF,产生一个状态叠合
|0m,0m〉|
1
2槡 m∑
2m-1
x=0
|x,0m〉;
Step3 做量子黑盒变换,完成αxmodN的并行计算
问题
1
2槡 m∑
2m-1
x=0
x,0m〉|
1
2槡 m∑
2m-1
x=0
x,αxmodN〉;
Step4 对第一寄存器再做在标准正交基 0〉,1〉,
…,2m-1〉上的量子 Fourier变换
1
2槡 m∑
2m-1
x=0
x,αxmodN〉
|
1
2m∑
2m-1
x=0
∑
2m-1
c=0
ωxc
2m
c,αxmodN〉
=
x=kr+t1
2m∑
2m-1
c=0
∑
r-1
t=0
∑
?(2m-t-1)/r」
k=0
ω(kr+t)c
2m
c,αtmodN〉
其中,t称为偏移量;
Step5 观察得到具体状态 c,xt〉,得到 c,利用连
分数方法计算出 r.然后判断 r是否为α的周期.如果
是,则算法结束.否则,返回 Step1,直到找到正确的 r为
止.
Shor通过证明算法运行一次成功的概率为4φ(r)/
π2r,因此 Shor整数求阶量子算法的成功率依赖于 ZN
中所选元素α模N的阶的大小.
基于 Shor整数求阶量子算法,可以对整数 N=pq
进行分解,具体如下:
选择一个整数α∈ZN,利用 Shor整数求阶量子算
63 电 子 学 报 2011年
法求出α模N的阶r.如果 r是奇数,算法需重新选择
α;如果 r是偶数,计算 αr/2( )+1modN,记为 d,当 d≠
-1时,计 算 并 输 出 gcd αr/2+1,( )N ,则 gcd
αr/2+1,( )N 是N的一个因子,否则需重新选择α并计
算α模N的阶.
4 新的整数分解量子算法
量子计算机之所以能快速计算出整数的阶,是因
为在 Shor整数求阶量子算法中运用了量子 Fourier变
换,通过量子 Fourier变换可将偏移量 t变成一个相位
因子,使得输入量子态的几率幅发生改变,即目标态被
观察到的概率变大,而非目标态被观察到的概率变小.
以下我们正是基于这一思想,给出一个新的整数分解
量子算法,通过多次运行量子 Fourier变换使得输入态
之间存在的关系转化为相位因子.
由于对任意α∈ZN,如果 gcd(α,N)≠1,则由 Eu
clidean算法可求出 N的一个因子为 gcd(α,N),因此,
以下我们不妨只讨论gcd(α,N)=1时整数 N=pq的分
解情况.
新整数分解量子算法:
Step1 N=pq,任意给定一个数α∈ZN和三个L
=「logN?维量子寄存器,其中α与N互素,量子寄存器
的初态都为|0L〉.
Step2 对前两个寄存器分别做在标准正交基 0〉,
1〉,…,N-1〉上的量子Fourier变换,产生叠加态:
0L〉0L〉0L〉|
1
N∑
N-1
x=0
∑
N-1
y=0
x〉y〉0L〉
Step3 完成函数 f(x,y)=αx的并行计算并将其
加到第三个寄存器中:
1
N∑
N-1
x=0
∑
N-1
y=0
x〉y〉0L〉|
1
N∑
N-1
x=0
∑
N-1
y=0
x〉y〉αx〉
再对第三个寄存器进行观测可以得到一个元素αt,其中
0≤t≤N-1,记α的阶为 r,由于αx=αx+ry=αtmodN,
故前两个寄存器的叠加态为 1
槡N∑
N-1
y=0
t-ry〉y〉αt〉.
Step4 对前两个寄存器分别做在标准正交基 0〉,
1〉,…,N-1〉上的量子Fourier变换,可以得到
1
槡N∑
N-1
y=0
t-ry〉y〉αt〉
|
1
槡N N∑
N-1
y=0
∑
N-1
t′=0
∑
N-1
y′=0
ω t-( )ry t′N ωyy′N t′〉y′〉αt〉
Step5 对前两个寄存器进行观测,得到 t′,y′.
Step6 如果 t′=0,返回Step1,重新选择α;如果 t′
≠0,则执行下一步.
Step7 计算 d=gcd(t′,N);
如果 d≠1,输出 d,算法结束;
如果 d=1,那么计算 r=(t′)-1y′modN,当 r是偶
数且αr/2≠ -1modN时,输出 gcd(αr/2+1,N),算法结
束;否则,返回 Step1,重新选择α.
以下分析算法的正确性,并计算算法成功的概率.
首先,分析经过第四步的变换之后,量子叠加态之
间存在的内在关系.
由于
∑
N-1
y=0
ωtt′Nωy y′-
( )rt′
N =
Nωtt′N,y′=rt′modN
0, y′≠ rt′mod
{ N
因此
1
槡N N∑
N-1
y=0
∑
N-1
t′=0
∑
N-1
y′=0
ω(t-ry)t′N ωyy′N t′〉y′〉αt〉
= 1
槡N∑
N-1
t′=0
∑
y′=rt′modN
ωtt′N t′〉y′〉αt〉.
从而,前两个寄存器中不满足 y′=rt′modN的量子
态 t′〉y′〉的几率幅变成 0,经过第四步之后,前两个
寄存器保留下的量子态 t′〉y′〉均满足 y′=rt′modN.
其次,讨论第(7)步是如何对整数进行分解的:
①如果 d≠1,那么 d N,又由于 N是两个素数的
乘积且t′≤N,因此可以对 N进行整数分解;
②如果 d=1,那么 t′存在一个逆元u∈ZN使得ut′
=1modN,由于 y′=rt′modN,故 uy′=urt′modN即r=
uy′modN.此时,当 r是偶数且αr/2≠ -1modN时,由引
理1可知,整数 N可以成功被分解;否则需要重新选择
α并求其模N的阶.
最后,由算法执行过程不难推出,保留下的量子态
每个被观察到的的概率是
pt′,y′=
1
Nω
tt′
N
2=1N,
因此,所保留下的量子态的概率之和仍为1.
5 新算法与Shor算法的性能对比分析
新算法的核心是量子 Fourier变换的多次运用.文
献[9]指出量子Fourier变换是一个酉变换,满足量子算
法所要求的可逆条件,在第三步内所使用的并行计算
同样也是一个可逆计算.就算法的本身所使用的变换
而言,该算法是正确的,在量子计算机可以得到有效的
实现.下面分别从算法成功率与资源消耗情况两个方
面,将新算法与 Shor算法进行对比.
算法成功率对比:
在Shor整数分解量子算法中,由推论1可知,得到
r之后能成功分解整数N的概率大于3/4,再根据第 3
节的求解过程可知,运行 Shor整数求阶量子算法一次
能够对整数 N=pq进行分解的成功概率p满足
3φ(r)/π
2r<p<4φ(r)/π
2r,
同样 Shor算法的成功率也依赖于 r的大小.
73第 1 期 付向群:具有高概率的整数分解量子算法
在新算法中,由第 4节对算法的分析过程可得定
理1.
定理1 新的整数分解量子算法运行一次成功的
概率满足
4N-φ( )N -4
4N ≤p<
N-1
N .
证明:由算法执行步骤可知,算法在两种情况下可
对整数 N进行分解.当 gcd(t′,N)≠1时,通过求 gcd
(t′,N)对 N进行分解;当 gcd(t′,N)=1时,通过求出
ZN中元素α的阶对N进行分解.
由于在集合{0,1,…,N-1}中与 N互素的元素的
个数是φ(N),因此新的整数分解量子算法的第6步中
观察到 t′〉不为 0〉且 gcd(t′,N)≠ 1的概率为
N-φ(N)-1
N ,此时,能对 N进行整数分解的概率p1=
N-φ(N)-1
N ;
观察到 t′〉满足 gcd(t′,N)=1的概率为φ(N)/
N,易知 t′在模N下存在一个逆元,亦即可以求出随机
数α的阶r,由引理2,此时能对 N进行整数分解的概
率p2满足
3φ( )N
4N ≤p2<
φ( )N
N .
综上所述,运行新算法一次能够对两个素数乘积的整
数进行整数分解的概率 p满足
4N-φ( )N -4
4N ≤p=p1+p2<
N-1
N .
证毕.
因 为 N = pq, 所 以 4N-φ(N)-44N =
4pq-(p-1)(q-1)-4
4pq >
3
4,因此,新算法运行一次具
有较高的成功概率.同时,由于φ( )r<r,
4φ(r)
π2r
<4
π2
<
3
4,所以 Shor算法运行一次成功的概率小于
3
4,因而有
定理2.
定理2 如果整数 N=pq,p,q是两个素数,那么
利用新算法对 N进行整数分解的成功概率高于Shor整
数分解量子算法.
新的整数分解量子算法的成功概率之所以大于
Shor整数分解量子算法,关键在于利用了多次量子
Fourier变换和变量代换,使 0〉态之外的非目标态的几
率幅变成0,那么再进行观测时,就能以很大的概率得
到对整数分解有用的量子态,而且成功率不再依赖于
ZN中所选元素的阶r的大小.
算法资源消耗情况对比:
在新的整数分解量子算法中,前五步是在量子计
算机上执行的,后两步是在经典计算机上执行的.由于
后两步均可在经典计算机上以多项式时间得到实现,
在资源消耗上可以忽略,因此新算法的资源消耗主要
在前五步上.前五步中使用的基本部件主要有模幂运
算和量子 Fourier变换,它们所需的量子逻辑门数文献
[9]、[11]、[12]做了比较详细的分析,基于这些研究结
果,我们可以给出新算法的资源消耗分析.
新的整数分解量子算法初始化 0〉态是 L量子比
特的,执行1个 Hadmard变换需要 O(L)规模的量子逻
辑门[9],实现1个量子Fourier变换需要 O(L2)规模的量
子逻辑门,因此,新算法中4个量子 Fourier变换仍然需
要 O(L2)规模的量子逻辑门.对于模幂运算,由于加法
运算和进位运算需要3L个量子逻辑门,每个模乘运算
需要 L个长为L的加法运算,利用二进制表示法计算
模幂运算需要2L步模乘运算,所以模幂运算所需要的
量子逻辑门数的规模为 O(L3)[11],新算法中只需要 1
次模幂运算,亦即只需要 O(L3)规模的量子逻辑门,因
此实现整个新算法的量子线路所需要量子逻辑门的规
模为 O(L3).
Shor整数分解量子算法初始化 0〉态是 m量子比
特的,算法中需要 2次量子 Fourier变换和 1次模幂运
算,实现2次量子 Fourier变换需要 O(m2)规模的量子
逻辑门,实现1次模幂运算所需要的量子逻辑门数规模
为 O(m3),因此,实现 Shor整数分解量子算法的量子线
路所需量子逻辑门规模也是 O(m3)[9].由于 L=
「logN?、N2≤2m≤2N2,即2L≤m≤2L+1,因此,在算法
实现上新的整数分解量子算法所需的量子逻辑门数与
Shor整数分解量子算法是同等规模的.
6 结束语
本文提出了一个新整数分解量子算法,该算法利
用多次量子 Fourier变换和变量代换使得除 0〉态之外
的非目标态的几率幅变成零,从而提高算法的成功概
率.与 Shor整数分解量子算法相比,算法具有更高的成
功概率,而且不再依赖于 ZN中所选元素阶r的大小;算
法的计算复杂性仍是多项式时间的;算法运行所需的
量子逻辑门数的规模为 O(L3).与经典计算一样,量子
整数分解算法中模幂运算也是最耗时的,因此如何优
化算法,提高量子模幂运算的运行效率有待进一步研
究.
参考文献:
[1]PW Shor.Polynomialtimealgorithmsforprimefactorization
anddiscretelogarithmsonaquantum computer[J].SIAM
JournalonComputing,1997,26(5):1484-1509.(preliminary
versioninFOCS1994)
83 电 子 学 报 2011年
[2]LKGrover.Afastquantummechanicsalgorithmfordatabase
search[A].Proceedingsof28thACMSymposiumonTheoryof
Computation[C].NewYork:ACMPress,1996.212-219.
[3]张健红,伍前红,邹建成,王育民.一种高效的群签名[J].
电子学报,2005,33(6):1113-1115.
ZhangJianhong,WuQianhong,ZouJiancheng,WangYu
min.Anefficientgroupsignaturescheme[J].ActaElectronica
Sinica,2005,33(6):1113-1115.(inChinese)
[4]许春香,肖国镇.门限多重秘密共享
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
[J].电子学报,
2004,32(10):1688-1689.
XuChunXiang,XiaoGuozhen.Athresholdmultiplesecret
sharingscheme[J].ActaElectronicaSinica,2004,32(10):
1688-1689.(inChinese)
[5]JPBuhler,HW Lenstra,CPomerance.Thedevelopmentof
thenumberfieldsieve[J].LectureNotesinMathematics
(Springer),1993,1554:50-94.
[6]董庆宽,傅晓彤.对大整数n=pq分解的一个有效的搜索
算法[J].电子学报,2001,29(10):1436-1438.
DongQingkuan,FuXiaotong.Aneffectivesearchingalgo
rithmforfactoringlargeintegern=pq[J].ActaElectronica
Sinica,2001,29(10):1436-1438.(inChinese)
[7]DMcAnally.ARefinementofShor’sAlgorithm[DB].Arxiv:
quantph/0112055v4,2002.
[8]潘承洞,潘承彪.初等数论(第二版)[M].北京:北京大学
出版社,2003.16-21.
PanChengdong,PanChengbiao.ElementaryNumberTheory
(thesecondedition)[M].Beijing:BeijingUniversityPress.
2003.16-21.
[9]MANielsen,ILChuang.QuantumComputationandQuantum
Information[M].Cambridge:CambridgeUniversity,2000.198
-223.
[10]AJMenezes,PCVOorschot,SAVanstone.Handbookof
AppliedCryptography[M].Canda:CRCPressLLC,1997.283
-312.
[11]CZalka.FastversionsofShor’squantumfactoringalgorithm
[DB].Quantph/9806084v1,1998.
[12]CZalka.Shor’salgorithmwithfewer(pure)qubits[DB].
Quantph/0601097v1,2006.
作者简介:
付向群 男,1985年生于江西进贤,解放军信息工程大学电子技
术学院,博士生,研究方向为量子密码.
Email:fuxiangqun@126.com
鲍皖苏 男,1966年生于安徽天长,解放军信息工程大学电子技
术学院,教授,博士生导师,主要研究方向为序列密码、公钥密码、量
子密码. Email:2004bws@sina.com
93第 1 期 付向群:具有高概率的整数分解量子算法