所谓素数，就是除了1和自身之外不再有其他整数因子的整数。例如，6不是一个素数，因为除了1和6之外，它还有因子2和3。而7则是一个素数，因为它仅有的因子就是1和7。不是素数的数叫做合数。 这个定义看上去简单，但对素数性质的研究却造就了无比艰深的数学分支。我国著名数学家陈景润关于歌德巴赫猜想的世界领先性成果，就是关于素数性质的。判定一个大数是不是素数（素性判定），以及将一个大整数分解成素因子的乘积（大数分解），是有关素数的两个经典的数学问题。这两个问题虽说很容易理解，但历经千百年无数学者的努力，仍旧拿不出非常有效的办法。近年来，随着互联网的普及和电子商务和电子政务的进展，越来越多的人开始关注素数，因为作为一种公钥密码体制，目前在普遍使用的RSA算法的安全性就建立在素因子分解问题的数学难解性的基础之上。 在计算机科学中，衡量一个问题的难易，使用的是解决这个问题的所有可能的算法在最坏情况下能够达到的最好性能（比如，某种基本运算步骤的总数或在某种抽象模型机上的运行时间）相对于问题规模（比如，描述这个问题所用的文字的长度）的渐进阶，学术上称之为“计算复杂性”。如果这个渐进阶可以被某个多项式“罩住”，那么这个问题被称为“多项式可解的”，也可以说这个问题属于P类。从数学上看，在问题规模足够大的情况下，P类的问题比不是P类的问题明显具有更高的求解效率。因此，为素性判定和大数分解问题寻找具有多项式复杂性的算法，无论在理论上还是在实用上都有巨大的意义。 突破就发生在本月。据报道，印度理工大学计算机科学系的三位学者近日提出了素性判定的一个多项式算法，在历史上首次以严格的数学证明宣告了素性判定问题属于P类。这一成果通过电子文稿的方式在互联网上向多位学者散发。这一领域的顶级权威，加州大学伯克利分校的Lenstra教授和贝尔实验室的Pomerance教授发表评论指出，这一成果是“正确的、巧妙的、优雅的”。 在三位学者的工作之前，在素性判定领域的主流算法都是“概率性”的。概率性算法不同于确定性算法。你可以期望对绝大多数的输入都得到正确的结果，但无法保证对所有输入一定得到正确的结果。在数学软件Mathematica里面实施素性判定的命令PrimeQ就是用著名的拉宾-密勒强伪素数判定算法实现的，它就是一种效率极高的概率性素性判定算法。 三位学者的工作的价值在于，他们提出的不是一种概率性算法而是一种确定性算法。能够以一种数学上的绝对精确性保证在多项式时间内完成素性判定。他们的算法被证明不会超过与待判定整数长度的12次幂成正比的一个多项式。如果能够利用上某些启发线索的话，其渐进阶还可能会降低到6次幂甚至3次幂。 当然，证明素性判定问题属于P类，并不直接威胁到现有的RSA公钥密码体制的安全性。但是，这毕竟是一个突破，很多有关素数的计算，从面貌到原则都会因此发生重大的改观。RSA公钥密码体制今后的命运如何，让我们拭目以待。（白硕）

关键字：