大数质因子分解的量子算法.pdfVIP

维普资讯 CN43一l258／TP 计算机工程与科学 2003年第 25卷第 1期 ISSN lO07．130X COMPUTERENGINEERING ＆ SCIENCE Vo1．25，No．1，2003 文章编号 ：1007—130X(2003)01—0023—03 大数质因子分解的量子算法 AQuantumAlgorithmforLargePrimeFactorization 霍红卫，潘 征 HUO Hong·wei，PAN Zheng (西安电子科技大学计算机学院，陕西 西安 710071l (SchoolofComputerScience，XidianUniversity，Xi’an710071，China) 摘 要 ：量子质因子分解算法是一种利用波的特性在量子环境下进行整数质 因子分解的新方法。 本文首先介绍了量子质因子分解的基本思想及其相关概念，然后分析并给 出了大数质因子分解的量子 算法，最后对量子算法的发展前景进行了展望。 Abstract：Thequantum factoringalgorithm isanewmethodusingthefeaturesofquantum wavestofactorizein— tegers．Inthispaper，an introductionofthefundamentalprinciplesofquantum factoringalgorithmsisgiventogether with somerelationalconcepts，followedbyananalysisofthefeaturesofthequantum factoringalgorithm．Finallythe prospectofthedevelopmentofquantum computation ispresented． 关键词 ：量子算法；质 因子分解；离散傅立叶变换 Keywords：quantum algorithm；primefactorization；discreteFouriertransform 中图分类号 ：TP301．6 文献标识码 ：A 1 引言 2 大数质因子分解 的量子算法 量子计算是近年来 国际上新兴 的最前沿学 所谓大数质因子分解 ，是指把一个大整数分解 科。必威体育精装版研究成果证实 ，量子计算机执行特定计 为所有质数 因子 的乘积。对于一个 n位的整数 算任务的能力要 比传统计算机高出幂指数倍-。。。 Ⅳ，传统的因子分解算法是用不大于、／Ⅳ，不小于2 1994年 ，ATT研 究院的PeterW．Shor提 出 的整数去除 Ⅳ，整个计算过程需要√N一2,,／2步运 了一种能比传统计算机运算速度快上幂指数倍的 算，最后可以找到 Ⅳ的全部质数因子。显然 ，计算 量子算法-2J，这个算法强大到足 以解开著名的公 所需步骤与这个大数 的数据位数成幂指数关系。 开密钥加密 RSA算法中的私有密钥 。Shor的算 随着 n的变大，计算步骤将是一个天文数字。 法为量子计算 的发展开辟 了道路。从此，世 界众 1994年，美 国ATT研究 院的PeterW．Shor 多研究小组加入该研究行列，在量子计算研 究领 发现 ，通过引入量子力学的基本原理 ，完成一个 n 域不断取得重大进 步。 位大数的质因子分解 ，可以达到多项式 的时间复 收稿 日期 ：2002—03—18；修订 日期 ：2002．05—29 基金项 目：国家 自然科学基金资助项 目