摘要
对可用于密码体制设计的NP完全问题———背包问题 ,进行了量子算法分析 .从复杂度理论角度出发 ,讨论了如何用量子搜索算法加速背包问题等NP完全问题的求解 .并从群论的角度与Shor的大数分解算法做了比较 ,讨论了影响算法速度一些因素 .
Speeding up knapsack problem, one of the NP complete problems, which could be used to design public-key cryptosystems, was discussed using quantum algorithm. How to use Grover's quantum searching algorithm to speed up the knapsack problem was talked about based on computational complexity theory. Comparisons of quantum searching algorithm with Shor's factoring algorithm were delivered and the factors that affected the performance of quantum algorithms were discussed from group theory point of view. The future of the quantum algorithms was also augmented.
出处
《北京航空航天大学学报》
EI
CAS
CSCD
北大核心
2004年第11期1088-1091,共4页
Journal of Beijing University of Aeronautics and Astronautics
基金
国家重点基础研究发展规划 973资助项目 (G19990 3 5 80 2 )
国家自然科学基金资助项目 (60 2 73 0 2 7
60 40 3 0 0 4)
中国科学院研究生创新与实践基金资助项目
关键词
量子计算
背包问题
复杂度理论
密码分析
Algorithms
Computational complexity
Fourier transforms
Iterative methods
Problem solving
Public key cryptography
