Shor算法不是一个确定性算法？

[牛河梁]

昨晚睡觉前重看了康托尔的实数不可数原始证明催眠。今天想起Shor算法。重新翻回来看。10+年前推过里面的量子傅立叶变换，被虐得今天看起来还记忆尤新。但实在想不起来当年“发现”了什么可数-不可数问题。

上网到处去找其它对Shor算法的解释。忽然又“发现”，Shor算法似乎不是一个确定性算法。而是依赖于要去试，只有碰狗屎运的时候才能蒙对答案？这一点到是很像NP。Shor是一个NP算法？

谁能帮助指正一下？

[forecasting]

你自己去看吧，我不知道你的不确定性算法是怎么定义的。NP=Non-deterministic polynomial。Non-deterministic algorithm不等于Non-deterministic polynomial algorithm，大得多了。Shor算法也没确定是NPC算法或者NP-hard算法。一般人认为素因子分解不应该是NPC或者NP-hard算法。

[牛河梁]

以前学量子计算的时候，关注Shor算法的量子部分，如量子傅立叶转换。这次从头到尾看完，发现最后一步确定周期r的算法要靠蒙，不是确定性算法。举例说，以下来自知乎：https://zhuanlan.zhihu.com/p/139329165

“
数论告诉我们此事发生的概率为1/log log r。若k/r有公因子（下面例子中给出这种情况），则计算失败，重新计算。但只要重复O(log log r)次，则得到r的概率无限接近于1。
”

直觉告诉我这是一个典型的不确定算法。不像如排序，不多于n^2操作一定能得出结果。

至于是不是NP，没仔细推。取决于r可能有多大。但不超过NP应该是安全的猜测。

你自己去看吧，我不知道你的不确定性算法是怎么定义的。NP=Non-deterministic polynomial。Non-deterministic algorithm不等于Non-deterministic polynomial algorithm，大得多了。Shor算法也没确定是NPC算法或者NP-hard算法。一般人认为素因子分解不应该是NPC或者NP-hard算法。

[AnonymityFreedom]

忽然又“发现”，Shor算法似乎不是一个确定性算法。

你想要说的是Shor算法是randomized algorithm?

在数论上randomized algorithm不稀奇。miller-rabin 就是monte-carlo算法。

[Caravel]

昨晚睡觉前重看了康托尔的实数不可数原始证明催眠。今天想起Shor算法。重新翻回来看。10+年前推过里面的量子傅立叶变换，被虐得今天看起来还记忆尤新。但实在想不起来当年“发现”了什么可数-不可数问题。

上网到处去找其它对Shor算法的解释。忽然又“发现”，Shor算法似乎不是一个确定性算法。而是依赖于要去试，只有碰狗屎运的时候才能蒙对答案？这一点到是很像NP。Shor是一个NP算法？

谁能帮助指正一下？

需要一个经典演算步骤，因数分解分解的反运算很快。多算几次就几乎肯定能得到。

[牛河梁]

需要一个经典演算步骤，因数分解分解的反运算很快。多算几次就几乎肯定能得到。

几乎可以和可以完全不一回事。这里要分解的数极其巨大。举例说2^2048 x 2^2048。只有一个中奖号码。几乎能得到大概率就是得不到。

[牛河梁]

你说的对。我把这词给忘了。做的不确定图灵机多了只记得不确定这个词。随机算法是求不确定图灵机的近似算法。但不保证最优解。这里见到随机算法，本能反应就是这是个不确定图灵机问题。

你想要说的是Shor算法是randomized algorithm?

在数论上randomized algorithm不稀奇。miller-rabin 就是monte-carlo算法。

[Caravel]

几乎可以和可以完全不一回事。这里要分解的数极其巨大。举例说2^2048 x 2^2048。只有一个中奖号码。几乎能得到大概率就是得不到。

当然不是随机猜啦，因数分解是基于period finding，简单的说，如果要分解的属 N= p x q.

取任意和N互素的数x, x mod N, x^2 mod N, x ^3 mod N 会呈现周期序列，欧拉发现这个周期T会是 (p-1)(q-1)一个的因子。

所以只要多试几个x，就可以把p, q求出来。到这一步经典计算机也可以用，但是周期finding的计算很慢。

量子计算机的作用在于可以快速找出序列的周期。

[pseudo]

再说，如果RSA是公认的“万无一失”的加密方法，而且Eve已经知道别人在用这个方法，这本身就已经很不安全了！他完全可以平时就列表所有已知的素数，用的时候只从里面去找，就大大减少时间了。这样一来，所谓的“量子”计算还有优势吗？

和你想象的不一样，素数是密集的，非常多。你的这种做法不能在数量级上降低分解难度。

[FoxMe]

这才是行家。

当然不是随机猜啦，因数分解是基于period finding，简单的说，如果要分解的属 N= p x q.

取任意和N互素的数x, x mod N, x^2 mod N, x ^3 mod N 会呈现周期序列，欧拉发现这个周期T会是 (p-1)(q-1)一个的因子。

所以只要多试几个x，就可以把p, q求出来。到这一步经典计算机也可以用，但是周期finding的计算很慢。

量子计算机的作用在于可以快速找出序列的周期。

[Caravel]

电脑能表现的整数有限，目前最大是2,147,483,647，完全可以把里面所有已知的素数列表存起来。

你这个是2^32-1， RSA2048 是 2^2048