有关于Raqcoin的信息
Shor算法在量子计算机上分解整数N的时间复杂度为 logNlogN,几乎是对已知最有效的经典因数分解算法的 ee 指数加速,这种加速有可能在量子计算机上中断如RSA的现代加密机制。
Shor算法要解决的主要问题是:给定一个整数N,找出它的质因数。即对一个给定的较大数 NN 在多项式时间内确定两个素因子 p1p1和 p2p2 满足 p1⋅p2=Np1⋅p2=N。 在介绍shor算法步骤之前,先介绍一些数论知识。
因此,Shor算法的核心在于,将大数分解的问题转化为找周期的问题(如下数论知识所示)。我们可以通过构造一个酉矩阵 Ux,N|j⟩|k⟩−>|j⟩∣∣xjkmodN⟩Ux,N|j⟩|k⟩−>|j⟩|xjkmodN⟩, 最终的结果满足 xr=1(modN)xr=1(modN)。
选择一个任意的数字,比如 a=2a=2 (<15)
gcd(a,N)=gcd(2,15)=1gcd(a,N)=gcd(2,15)=1
找函数 f(x)=axmodNf(x)=axmodN 的周期,使得 f(x+r)=f(x)f(x+r)=f(x)
通过量子电路图运算得到 r=4r=4
gcd(ar2+1,N)=gcd(5,15)=5gcd(ar2+1,N)=gcd(5,15)=5
gcd(ar2−1,N)=gcd(3,15)=5gcd(ar2−1,N)=gcd(3,15)=5
N=15N=15 分解得到的质数结果为 3 和 5,分解完成。
<p background-color:#fcfcfc;"="" style="padding: 0px; margin-top: 0px; margin-bottom: 10px; list-style: none; line-height: 25px; background-color: rgba(255, 255, 255, 0.5); font-family: "Microsoft YaHei"; white-space: normal; color: rgb(64, 64, 64); background-image: none !important; background-position: initial !important; background-size: initial !important; background-repeat: initial !important; background-attachment: initial !important; background-origin: initial !important; background-clip: initial !important;">Shor算法的量子电路如下图所示: