背景详情

有关于Raqcoin的信息

当前位置:首页>背景详情

② Shor's algorithm(秀尔算法/舒尔算法)介绍

时间:2022-01-22   访问量:1750

Shor算法在量子计算机上分解整数N的时间复杂度为 logNlogN,几乎是对已知最有效的经典因数分解算法的 ee 指数加速,这种加速有可能在量子计算机上中断如RSA的现代加密机制。

Shor算法要解决的主要问题是:给定一个整数N,找出它的质因数。即对一个给定的较大数 NN 在多项式时间内确定两个素因子 p1p1和 p2p2 满足 p1⋅p2=Np1⋅p2=N。 在介绍shor算法步骤之前,先介绍一些数论知识。

f(x)=axmodNf(x)=axmodN


因此,Shor算法的核心在于,将大数分解的问题转化为找周期的问题(如下数论知识所示)。我们可以通过构造一个酉矩阵 Ux,N|j⟩|k⟩−>|j⟩∣∣xjkmodN⟩Ux,N|j⟩|k⟩−>|j⟩|xjkmodN⟩, 最终的结果满足 xr=1(modN)xr=1(modN)


  1. 选择一个任意的数字,比如 a=2a=2 (<15)

  2. gcd(a,N)=gcd(2,15)=1gcd⁡(a,N)=gcd(2,15)=1

  3. 找函数 f(x)=axmodNf(x)=axmodN 的周期,使得 f(x+r)=f(x)f(x+r)=f(x)

  4. 通过量子电路图运算得到 r=4r=4

  5. gcd(ar2+1,N)=gcd(5,15)=5gcd(ar2+1,N)=gcd(5,15)=5

  6. gcd(ar2−1,N)=gcd(3,15)=5gcd(ar2−1,N)=gcd(3,15)=5

  7. 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算法的量子电路如下图所示:


../images/shor.png


上一篇:① ECC椭圆曲线非对称加密原理

下一篇:③ 后量子密码学PQC(Post-Quantum Cryptography)介绍

发表评论:

评论记录:

未查询到任何数据!

免责声明

本站的内容为ABC爱好者收集编辑,仅供参考学习,不能作为实际操作使用!

浏览本站后,你的任何尝试都与站长本人无关,盈亏自负,也请为自己的行为负责。

本站提及的所有内容和项目,请自行判断风险,不作为任何投资建议。

本站除捐助外,不存在任何的交易以及售卖行为,请擦亮眼睛谨防被骗!

投资有风险,交易需谨慎。如果你无法认同上面的内容,请关闭本页面并停止浏览本站!

免责声明

微信扫一扫

微信联系
返回顶部