用分组法改进Shor算法的可能性

Possibility to improve Shor algorithm with grouping algorithm

分组算法被认为有可能降低经典的Shor算法复杂度至线性复杂度,且可能改善波粒二象计算机的计算能力。该文利用包括数论与概率论在内的纯数学方法,分析了这种想法的可能性。分2种情况讨论:1)底数变量是随机选取的方式,该思路与Shor的初衷是相吻合的;2)底数变量是有侧重选取的情形。在第2)种情形下,证明了对于任意给定的自然数k,存在某个N不符合线性约束,并对这种N在正整数中的分布作了讨论。总之,在这2种情况下,分组法都不能够成为降低Shor算法复杂度至线性复杂度的有效算法。Shor算法依然是已知的大数分解的算法中最优的算法。

The grouping algorithm might be used to reduce the complexity of the traditional Shor algorithm to linear complexity, and to enhance the calculate capacity of duality computers. This paper analyzes this possibility mostly based on mathematical theoretical analysis, applying number theory and probability theory. The work discusses mainly two cases： 1） bases randomly selected （in accordance to the original idea of Shor）; 2） some chosen with higher probabilities. In the second case, certain N is proved not to satisfy the linear restriction for any arbitrary k, and the distribution of such N among positive integers is also discussed. In conclusion, the grouping method is not effective in both cases. The Shor algorithm is still the optimal method for factoring large numbers.