有人可以提供一个外行的术语解释它的工作原理，以及为什么它依赖于量子计算吗？
请记住，虽然我有点理解量子计算的基本知识（即，它使用光子而不是电子，并且比特被可以为0、1或两者叠加的量子位代替）对此一无所知。我只知道与传统的计算机制相比，它应该超级快。
#1 楼
要回答的问题是“ N是P * Q的乘积吗？”我认为了解Shor的最简单方法是想象两个正弦波，一个长度为P，一个长度为Q。假设P和Q是互质的，那么上面的问题也可以得到回答： P与Q重复本身重叠吗？”根据简单的观察，我们可以快速地确定答案，我们可以找出数字线上任意给定点的每个波的相位。 （请记住，相位是“此点沿着图形有多远？”，通常以度为单位； 90度= 1/4旋转）如果我们查看点N，则如果P和Q的相位是N的因数，则它们的相位必须为0（否则将存在除法N / Q或N / P的余数）。 Shor只是测试了N点上P的相位是否等于P == 0的相位。事实证明，相位估计对于量子计算机而言非常容易，因此它是构建乘数分解机的好工具。有关更多信息，请参见http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm。
评论
$ \ begingroup $
这实际上是一个很好的解释方式。
$ \ endgroup $
–多项式
2012年10月10日7:31
$ \ begingroup $
要回答的问题是“哪个P和Q至少2是N的乘积？”而不是“ N是P * Q的乘积吗？”。对于以后的版本，我们有非常有效的算法，即经典计算机上Log（N）中的多项式。
$ \ endgroup $
–fgrieu♦
2012年10月10日10:39
评论
看看scottaaronson.com/blog/?p=208我没有资格提供答案，但是您可能正在寻找以下文章：arstechnica.com/security/2012/09/…
我认为Shor的算法即使输入不是半素也可以工作。 $ \：$
不，因为它还可以有效地解决离散对数。 $ \：$
我认为Shor的算法会评估$ a ^ x \ pmod {n} $的周期，其中$ \ gcd {（a，n）} = 1 $。这在经典计算机上效率不高，但是当在量子计算机上运行时，就会发生奇迹，并且我们得到多项式时间中概率为$ 0.5 $的平方同余。我想奇迹的部分是您要问的..但这需要我以外的物理和数学知识。