量子那些事儿 关注
手机版

量子计算将能分解任意极大整数,RSA加密或成摆设

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

量子计算将能分解任意极大整数,RSA加密或成摆设

雪花又一年 2018-05-15 14:43:17 浏览95 评论0

摘要: 就算是一台超级计算机有可能在数年的时间内计算出任意质因数,这也是得不偿失的。为了科学地解决这个问题,麻省理工学院(MIT)的科学家找到了明确的方法。今天,《科学》杂志最新发表的一篇论文显示,量子计算机有史以来第一次以可扩展的方式,实现了Shor算法。

量子计算将能分解任意极大整数,RSA加密或成摆设

就算是一台超级计算机有可能在数年的时间内计算出任意质因数,这也是得不偿失的。为了科学地解决这个问题,麻省理工学院(MIT)的科学家找到了明确的方法。今天,《科学》杂志最新发表的一篇论文显示,量子计算机有史以来第一次以可扩展的方式,实现了Shor算法。

据外媒Engadget报道,MIT和 Innsbruck大学的计算机科学家组装了一台5量子比特的量子计算机,它将能够用Shor算法完成对数字15的质因数分解。他们研发了一台量子计算机原型,然后使用一系列离子,借助激光脉冲来在4个量子比特上执行Shor算法,令其分解数字,第5个量子比特则用于储存和输出结果。目前的结果是,这台计算机不仅能够比现有量子系统更高效地计算出方案,而且区间缩放相对容易。

据维基百科解释,Shor算法(秀尔算法)是一个在1994年发现,以数学家彼得·秀尔命名,针对整数分解的量子算法(在量子计算机上面运作的算法)。比较不正式的表述是,它解决题目如下:给定一个整数N,找出他的质因数。

在一个量子计算机上面,要分解整数N,秀尔算法的运作需要多项式时间(时间是log N的某个多项式这么长)。更精确的说,这个算法花费O((log N)3)的时间,展示出质因数分解问题可以使用量子计算机以多项式时间解出,因此在复杂度类BQP里面。这比起传统已知最快的因数分解算法,普通数域筛选法,其花费次指数时间——大约O(e1.9 (log N)1/3 (log log N)2/3),还要快了一个指数的差异。

秀尔算法的重要性不言而喻,实现它我们就有望破解已被广泛使用的公开密钥加密方法——RSA加密算法。RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用,其高度可靠的秘密在在于:对极大整数做因数分解的极大难度。也就是说,对一极大整数做因数分解愈困难,RSA算法愈可靠。但是,假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。此前,世界上还没有任何攻击RSA算法的可靠方式。

然而,秀尔算法展示了因数分解这问题在量子计算机上可以很有效率地解决,所以一个足够大的量子计算机可以破解RSA。这对于建立量子计算机和研究新的量子计算机算法,是一个非常大的动力。


原文发布时间为:2016-03-06
本文作者:温晓桦
本文来源:雷锋网,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】云栖社区技术交流群汇总,阿里巴巴技术专家及云栖社区专家等你加入互动,老铁,了解一下?  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注25
关注
服务底层使用经国家密码管理局检测认证的硬件密码机,通过虚拟化技术,帮助用户满足数据安全方面的... 查看详情
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
阿里云流计算(Aliyun StreamCompute)是运行在阿里云平台上的流式大数据分析... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
建站4折

建站4折