1. 全栈程序员必看首页

【量子计算-算法】shor大数分解

全栈程序员-站长 • • 未分类 • 阅读 1

【量子计算-算法】shor大数分解shor 大数分解算法

shor大数分解算法

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

Classical part[edit]

  1. Pick a random number a < N.
  2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
  3. If gcd(a, N) ≠ 1, then this number is a nontrivial factor of N, so we are done.
  4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:
    f(x)=axmodN,{\displaystyle f(x)=a^{x}{\bmod {N}},}f(x)=a^{x}{\bmod {N}},

    i.e. the order r{\displaystyle r}r of a{\displaystyle a}a in (ZN)×{\displaystyle (\mathbb {Z} _{N})^{\times }}(\mathbb {Z} _{N})^{\times }, which is the smallest positive integer r for which f(x+r)=f(x){\displaystyle f(x+r)=f(x)}f(x+r)=f(x), or f(x+r)=ax+rmodN≡axmodN.{\displaystyle f(x+r)=a^{x+r}{\bmod {N}}\equiv a^{x}{\bmod {N}}.}{\displaystyle f(x+r)=a^{x+r}{\bmod {N}}\equiv a^{x}{\bmod {N}}.}

  5. If r is odd, go back to step 1.
  6. If a r /2 ≡{\displaystyle \equiv }\equiv  −1 (mod N), go back to step 1.
  7. gcd(ar/2 + 1, N) and gcd(ar/2 – 1, N) are both nontrivial factors of N. We are done.

For example: N=15,a=7,r=4{\displaystyle N=15,a=7,r=4}N=15,a=7,r=4, gcd(72±1,15)=gcd(49±1,15){\displaystyle \mathrm {gcd} (7^{2}\pm 1,15)=\mathrm {gcd} (49\pm 1,15)}\mathrm {gcd} (7^{2}\pm 1,15)=\mathrm {gcd} (49\pm 1,15), where gcd(48,15)=3{\displaystyle \mathrm {gcd} (48,15)=3}\mathrm {gcd} (48,15)=3, and gcd(50,15)=5{\displaystyle \mathrm {gcd} (50,15)=5}\mathrm {gcd} (50,15)=5.

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

【量子计算-算法】shor大数分解

参考文献：

[1] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[M]. Society for Industrial and Applied Mathematics, 1997.

 


版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225621.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 上午8:54
下一篇 2026年3月17日 上午8:54


相关推荐

  • 多服务器共享session的方法

    多服务器共享session的方法

    多服务器共享session的方法伴随网站业务规模和访问量的逐步发展，原本由单台服务器、单个域名的迷你网站架构已经无法满足发展需要。此时我们可能会购买更多服务器，并且启用多个二级子域名以频道化的方式，根据业务功能将网站分布部署在独立的服务器上；或通过负载均衡技术（如：DNS轮询、Radware、F5、LVS等）让多个频道共享一组服务器。OK，头脑中我们已经构思了这样的解决方案，不过进入深入开发后新的技术问题又随之…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月13日
    34
  • 防止页面url缓存中 ajax中post 请求的处理方式

    防止页面url缓存中 ajax中post 请求的处理方式

    一般我们在开发中经常会用到Ajax请求，异步发送请求，然后获取我们想要的数据，在Ajax中使用Get请求数据不会有页面缓存的问题，而使用POST请求可是有时候页面会缓存我们提交的信息，导致我们发送的异步请求不能正确的返回我们想要的数据。

    全栈程序员-站长的头像 全栈程序员-站长
    2022年2月24日
    45
  • <span role="heading" aria-level="2">557 原型prototype和原型链__proto__：原理，函数的三种角色，for in，手写new

    557 原型prototype和原型链__proto__：原理，函数的三种角色，for in，手写new

    557 原型prototype和原型链__proto__：原理，函数的三种角色，for in，手写new向对象底层运行机制的三句话*面向对象底层运行机制的三句话：*1.每一个函数（普通函数、内置类/构造函数、自定义类/构造函数）都具备一个属性:prototype[原型]，属性值是一个对象[浏览

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月3日
    22
  • 4个基本不等式的公式高中_高中4个基本不等式的公式

    4个基本不等式的公式高中_高中4个基本不等式的公式

    4个基本不等式的公式高中_高中4个基本不等式的公式高中4基本不等式：√[(a2+b2)/2]≥(a+b)/2≥√ab≥2/(1/a+1/b)。平方平均值≥算术平均数≥几何平均数≥调和平均数。基本不等式的两个技巧“1”使用。如果标题中有两个公式，则它们之和为常数，要求这两个公式的倒数之和的最小值，常用所把这个公式乘以1，然后把1让我们使用上一个常量，可以通过扩展这两个公式来计算。如果你知道两个公式的倒数之和是常数，求两个公式之和的最小值，方法同上。…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月27日
    108
  • matlab保存图片函数后突变分辨变化,MATLAB总结 – 图片保存「建议收藏」

    matlab保存图片函数后突变分辨变化,MATLAB总结 – 图片保存「建议收藏」

    matlab保存图片函数后突变分辨变化,MATLAB总结 – 图片保存「建议收藏」I.Matlab中保存图片的方法1.一种是出来图形窗口后手动保存(这儿又可以分两种)：1.1直接从菜单保存，有fig,eps,jpeg,gif,png,bmp等格式。1.2edit——〉copyfigure，再粘贴到其他程序。2.另一种是用命令直接保存(这里也有两种)：2.1用saveas命令保存图片。saveas的三个参数：(1)图形句柄，如果图形窗口标题栏是“Figure3…

    全栈程序员-站长的头像 全栈程序员-站长
    2025年11月3日
    6
  • 分享 Claude Code 实际使用的一些经验（1） 全栈程序员

    分享 Claude Code 实际使用的一些经验（1）

    分享 Claude Code 实际使用的一些经验（1）

    Ai探索者的头像 Ai探索者
    2026年3月15日
    3

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号