访问量： 88 次浏览
在保存数字信息的密码体系中，素数是极有价值的商品， 例如信用卡卡号在网络上的加密。大多数加密方法的基础都是把两个非常大的素数相乘， 而破解加密信息的关键就在于找出此一乘积的两个因子， 这是不可能完成的任务，因为要花费的时间实在太长了。 即使数值运算最快的计算机，也需要几天、几星期或几年， 才能找到一个长达几百位数字的素因子，所以若是用了正确的软件， 网络商务使用者就不必担心他们的信用卡卡号会被窃取。 只有那些实际拥有密钥的人，也就是知道正确素因子的人，才能解开加密的信息。
使用这种加密方法时，必须确定用来编密码的数真的是素数。 如果不是，它还可以被分解为更小的数字时， 最后乘积的因子分解就不是只有单一解了（两个非素数6和14相乘等于84， 这个乘积可以被分解为不同的一对因子，例如3和28或7和12）。 在这种情况下，有些密钥是正确的，有些则是错误的， 为了避免混淆，使用之前，必须确认可能的密钥皆为素数。
但要证明一个数是否为素数并不是件简单的工作， 现有的可证明某个数是素数的算法不是非常耗时， 就是只能证明一个正整数是素数的概率的大小。 相关人士莫不渴望能出现一种算法，既迅速， 又可以百分之百地确定一个数字是否为素数。
3位印度计算机科学家组成的小组正在进行这项任务。 印度理工学院坎普尔分校的阿加瓦尔和他的两个学生卡亚勒、萨森纳， 利用并扩充了费马定理，即所谓的小定理，而非比较有名的“最后”定理， 来检定数字是否为素数。他们设计好方法后， 计算机程序的分析显示出了惊人的结果：检验素数所需的时间不会随着数字变大而呈指数增加， 只需要多项式级的执行时间。
这几位科学家在网络上宣布了研究成果，不出几日， 全球新闻媒体都注意到了这个消息。他们赞扬这项发现是重大的突破， 但这实在有点夸大其词。尽管3人在理论方面的确有些突破， 但在数学领域，“只”（就像“只是”多项式级）这个字眼极具相对意味。 这位印度教授和其学生提出的算法所需的执行时间， 的确是yv的多项式，表示该目标整数的位数。但它与成正比， 这意味着检验一个30位的素数（就密码而言是极小的密钥），需要301外运算步骤。
想想迄今已知的100个最大的素数， 每个数的长度都超过4万位（目前世界纪录中最大的素数有400万位）， 我们立即就可以明白，这个算法的发现与实际运用基本上是两回事。
然而，这项意外结果仍在相同领域人士间造成了轰动， 3位科学家的确提出了美丽又创新的概念坦白地说， 这项算法在应用上仍然太费时，但它已经打破僵局， 专家相信不久就能找出更有效率的计算方式。先撇开这点不谈， 至少大家不需要担心信用卡卡号是否安全，因为他们发现的这个方法不能用于破解加密密码。