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