AKS素性测试算法---兼谈P和NP问题

曹正军

      Manindra Agrawal (1966---), 印度人, 印度理工学院坎普尔分校教授. 2002年与学生Kayal和Saxena共同设计了一个确定型的多项式时间素性测试算法, 简称AKS算法.  因为这项工作, 他们获得了2006年的哥德尔奖.

 P和NP问题

     Stephen Cook (1939---), 多伦多大学教授, 1966年获哈佛大学博士学位(导师王浩). 他于1971年正式引入了P和NP问题, 1982年获图灵奖.  John Hopcroft (1939---), 美国人, 康奈尔大学教授, 1964年获斯坦福大学博士学位(导师Richard Mattson). 他深入研究了NP问题, 因为在算法设计和数据结构方面的工作, 1986年获图灵奖.

      图灵机是一种假想的设备, 它有一条记忆带、一个读写针头、一些约定的符号和运算规则. 对记忆带的长度没有限制, 要多长就有多长. 图灵机有两种, 一种是确定型的, 另一种是非确定型的. 确定型图灵机的每一步运算是明确无误的, 同样的输入必将得到同样的结果. 非确定型图灵机的有些步骤是不确定的, 需要抛币(俗称``抓阄")来选择后续的操作, 同样的输入会得到不同的结果. 能够用确定型图灵机在多项式时间内解决的问题称为P问题, 能够用非确定型图灵机在多项式时间内解决的问题称为NP问题. 一个NP问题能不能转化成P问题呢? 这就是计算机科学界著名的P和NP是否相等的问题.  

      维基百科为P和NP问题设立了一个专门的网页 

http://en.wikipedia.org/wiki/P_versus_NP_problem

  一个问题是P的, 是不是就意味着它是容易的呢? 关于这一点, 有两种基本解释:   1) 一个理论上被证明是P的算法可能含有较大的常数因子, 导致算法失效; 2) 有些问题不适合图灵机模型. 理论上, 算法的运行时间是用位操作的次数来计量的, 不包含在磁性材料上读、写数据的时间. P和NP定义中的这个缺陷还没有被广泛知晓. 实质上, 一个需要巨大存储空间的算法是不可能有效实现的, AKS算法就是一个典型的例子.

      AKS算法应该是P和NP理论研究的巅峰之作, 其后很难再有这类简洁的证明啦. 然而, AKS算法在实际中难以践行的窘态恰恰说明P和NP概念本身的历史局限性, 也印证了一个观点--P和NP问题没有大家想象的那么重要!

      下面这个网址收集了一些关于P和NP问题的``论文"

            http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

支持和反对P=NP的, 几乎各占一半.  很多论文充斥着杂乱的符号、似是而非的概念、理想化的模型、生僻的方法, 但都没有解决一个实际问题.

参考文献

M. Agrawal, N. Kayal, N. Saxena:  PRIMES is in P,  Annals of Mathematics, 160 (2), 81-793. 2004.

Z. J. Cao: A note on the storage requirement for AKS primality testing algorithm, Cryptology ePrint Archive Report 449, 2013.

H. Li : The analysis and implementation of the AKS algorithm and its improvement algorithms, Available at: \verb|opus.bath.ac.uk/16757/1/CSBU-2007-09.pdf|

本文摘自作者的书稿《现代密码算法概论》