Journal of Tsinghua University(Science and Technology)
Possibility to improve Shor algorithm with grouping algorithm
Liu Li
Abstract
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.