| 背包问题的量子算法分析 |
| |
| 引用本文： | 吕欣,冯登国.背包问题的量子算法分析[J].北京航空航天大学学报,2004,30(11):1088-1091. |
| |
| 作者姓名： | 吕欣 冯登国 |
| |
| 作者单位： | 中国科学院究生院 信息安全国家重点实验室, 北京 100039 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划)，国家自然科学基金，中国科学院研究生创新项目 |
| |
| 摘 要： | 对可用于密码体制设计的NP完全问题——背包问题，进行了量子算法分析.从复杂度理论角 度出发，讨论了如何用量子搜索算法加速背包问题等NP完全问题的求解.并从群论的角度与S hor的大数分解算法做了比较，讨论了影响算法速度一些因素.对量子算法的特性和前景做了展望.
|
| 关 键 词： | 量子计算 背包问题 复杂度理论 密码分析 |
| 文章编号： | 1001-5965(2004)11-1088-04 |
| 收稿时间： | 2004-06-25 |
| 修稿时间： | 2004年6月25日 |
Quantum algorithm analysis of knapsack problem |
| |
| Lü,Xin,Feng Denggu.Quantum algorithm analysis of knapsack problem[J].Journal of Beijing University of Aeronautics and Astronautics,2004,30(11):1088-1091. |
| |
| Authors: | Lü Xin Feng Denggu |
| |
| Institution: | State Key Laboratory of Information Security, Graduate School, Chinese Academic of Science, Bejing 100039, China |
| |
| Abstract: | 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 in the later. |
| |
| Keywords: | quantum computation knapsack problem complexity theory cryptanalysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京航空航天大学学报》浏览原始摘要信息 |
| 点击此处可从《北京航空航天大学学报》下载免费的PDF全文 |
