确认素数的工程浩大

确认素数的工程浩大


发布日期: 2016-10-24 更新日期: 2016-11-09 编辑:xuzhiping 浏览次数: 4000

标签:

摘要: 在保存数字信息的密码体系中,素数是极有价值的商品,例如信用卡卡号在网络上的加密。大多数加密方法的基础都是把两个非常大的素数相乘,而破解加密信息的关键就在于找出此一乘积的两个因子,这是不可能完成的任务,因为要花费的时间实在太长了。即使数值运算最快的计算机,也需要...

在保存数字信息的密码体系中,素数是极有价值的商品,例如信用卡卡号在网络上的加密。大多数加密方法的基础都是把两个非常大的素数相乘,而破解加密信息的关键就在于找出此一乘积的两个因子,这是不可能完成的任务,因为要花费的时间实在太长了。即使数值运算最快的计算机,也需要几天、几星期或几年,才能找到一个长达几百位数字的素因子,所以若是用了正确的软件,网络商务使用者就不必担心他们的信用卡卡号会被窃取。只有那些实际拥有密钥的人,也就是知道正确素因子的人,才能解开加密的信息。

使用这种加密方法时,必须确定用来编密码的数真的是素数。如果不是,它还可以被分解为更小的数字时,最后乘积的因子分解就不是只有单一解了(两个非素数6和14相乘等于84,这个乘积可以被分解为不同的一对因子,例如3和28或7和12)。在这种情况下,有些密钥是正确的,有些则是错误的,为了避免混淆,使用之前,必须确认可能的密钥皆为素数。

但要证明一个数是否为素数并不是件简单的工作,现有的可证明某个数是素数的算法不是非常耗时,就是只能证明一个正整数是素数的概率的大小。相关人士莫不渴望能出现一种算法,既迅速,又可以百分之百地确定一个数字是否为素数。

3位印度计算机科学家组成的小组正在进行这项任务。印度理工学院坎普尔分校的阿加瓦尔和他的两个学生卡亚勒、萨森纳,利用并扩充了费马定理,即所谓的小定理,而非比较有名的“最后”定理,来检定数字是否为素数。他们设计好方法后,计算机程序的分析显示出了惊人的结果:检验素数所需的时间不会随着数字变大而呈指数增加,只需要多项式级的执行时间。

这几位科学家在网络上宣布了研究成果,不出几日,全球新闻媒体都注意到了这个消息。他们赞扬这项发现是重大的突破,但这实在有点夸大其词。尽管3人在理论方面的确有些突破,但在数学领域,“只”(就像“只是”多项式级)这个字眼极具相对意味。这位印度教授和其学生提出的算法所需的执行时间,的确是yv的多项式,表示该目标整数的位数。但它与成正比,这意味着检验一个30位的素数(就密码而言是极小的密钥),需要301外运算步骤。

想想迄今已知的100个最大的素数,每个数的长度都超过4万位(目前世界纪录中最大的素数有400万位),我们立即就可以明白,这个算法的发现与实际运用基本上是两回事。

然而,这项意外结果仍在相同领域人士间造成了轰动,3位科学家的确提出了美丽又创新的概念坦白地说,这项算法在应用上仍然太费时,但它已经打破僵局,专家相信不久就能找出更有效率的计算方式。先撇开这点不谈,至少大家不需要担心信用卡卡号是否安全,因为他们发现的这个方法不能用于破解加密密码。

关注公众号
获取免费资源

随机推荐


Copyright © Since 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org