资源描述：
《量子信息讲座续讲第一讲量子计算中的因子分解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、讲座量子信息讲座续讲3第一讲量子计算中的因子分解张镇九张昭理(华中师范大学物理系相对论研究中心武汉430070)摘要因子分解对所有的现行计算机而言是难解的.这是现在通用的公共加密系统的基础.文章介绍了在量子计算机上进行的Shor量子算法,即利用量子态的相干叠加和纠缠特性以及量子逻辑门实现量子计算的方法;并着重从理论原理和实验实现这两方面说明利用余因子函数和离散傅里叶变换使这种量子算法对因子分解是有效的.关键词量子计算,量子算法,因子分解,余因子函数,离散傅里叶变换FACTORIZATIONINQUANTUMCOMPU
2、TATIONZHANGZhen2JiuZHANGZhao2Li(CenterforRelativityStudies,DepartmentofPhysics,CentralChinaNormalUniversity,Wuhan430070)AbstractFactorizationisanon2polynomialproblemforthepresentcomputers.Itisthebasisofthepubliccryptography.Inthispaper,wediscusstheShor’squantum
3、algorithmonaquantumcomputer,whichistheal2gorithmusingthecoherenceandentanglementofquantumstatesonwhichthequantumlogicgatesact.Wethenemphasizefromthetheoreticalprincipleandtheexperimentalrealizationtheefficiencyofthequantumfactoriza2tionbyusingtheremainderfuncti
4、onanddiscreteFouriertransform.Keywordsquantumcomputation,quantumalgorithm,factorization,remainderfunction,discreteFouriertransform量子系统、模拟核试验等).1引言现行的计算机,对正整数的因子分解是难解问题,即所需要的计算时间随要计算的数的位数的增密码现在是政府、银行、公司和私人保护其信息加以指数方式增长.这种状况在经典计算范围内不交换的重要手段.由于计算机因特网、传递数字签名可能从本质上解
5、决.现在经典计算机上使用的是(它可被证认而不可被复制)、电子商务和数字现金1977年Rivest,Shamir和Adelman三人所发明的的推广,保密系统的安全性日益重要.现在所用的计RSA公共加密系统,它利用两个大素数的乘积难以算机网络的公共加密系统,多是以大数因子分解的分解来加密.困难为基础.将两个30位的素数的乘积进行因子分在量子计算机上进行的Shor量子算法对因子解,目前世界上运算速度最快的巨型计算机约需要分解是有效的,即对正整数的因子分解所需要的计宇宙的寿命这样长的时间.在同样运算速度的量子算时间随要计算的
6、数的位数的增加以多项式方式增-8计算机上,上述问题10s可解决.可见现行的公共长.当正整数的位数很大时,以位数的指数方式增长加密系统在量子计算机面前无任何秘密可言,而以和以位数的多项式方式增长有巨大的差别.这一方全新的量子概念为基础的量子加密系统却有很好的面说明量子计算的一个巨大优越性;另一方面,这将安全性.这也就是为什么美、英、俄、日、德以及我国3国家自然科学基金资助项目都很重视量子信息、量子计算和量子通信方面的研2000-02-22收到初稿,2000-04-26修回究的重要原因之一(其他原因如计算速度高、能模拟·
7、560·物理©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net从根本上破坏所有现行的计算机上使用的公共安全数d和e,使(de-1)可被(p-1)(q-1)除尽.张三加密系统的安全性.本文着重从理论原理和实验实将p和q的乘积N(不是p,也不是q)和e这两个[1—9]现这两方面说明Shor量子算法中的因子分解数作为公钥公布,将d作为私钥保存.李四将要发的有效性,显示量子计算的巨大优越性.
8、尽管量子算送给张三的信息用数m表示,利用张三的公钥Nee法可提供新的量子公共安全加密系统,但是不在本和e,将m编为密码c=mmodN(意思是:c是m文讨论之列.被N除的余数),发给张三.张三收到c,利用私钥dd量子算法中的因子分解的关键是:将若干个正解密,以得到m=cmodN.下面用较小的数为例加整数因子的乘积分解为各因子等效于求余因子函数以说
