2. 质数和因数分解

你可以对15进行因数分解，得出15×1或5×3。24这个数可等于24×1、 12×2 、8×3或6×4。但是你只能把17写作17×1。17是一个质数，即只能把它写作1和自身乘积的数。最开始的几个质数是2、3、5、7、11、13、17、19。质数有无限多个。已知的最大质数（在我写作之时）是一个12 978 189位的数，它开始的几位是316 470 269 330 255 923 143 453 723…

怎么判断一个数是否是质数？例如要判断1 123 467 619是否是质数，你需要遍历所有小于1 123 467 619的数，看看是否有能整除它的数。事实上你只需要检查到33 518（1 123 467 619的平方根）就可以了。听起来是挺快，可是你如何判断下面这个数是否为质数？

8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

早在古希腊就出现了判定质数的算法，但直到20世纪70年代才出现对几百位数有效的算法。这些算法基于数学中一个叫数论的领域的研究成果，在检查时需要使用随机生成的数。虽然这些算法在实践中表现很好，但是不依赖于随机生成数的质数判定算法直到2002年，才由一位印度教授曼尼达·阿加拉瓦尔带领他的学生尼拉吉·卡亚尔和尼汀· 萨克斯纳发现，从而把该问题归属于P类问题。

这些算法虽然能告诉我们

8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

这个数不是质数，但令人惊奇的是，它们不能告诉你这个数的因子有哪些，也就是说不能对其因数分解。

我们有判定质数的有效算法，但是没有分解因数的有效算法。

因数分解是一个NP问题，因为如果你看到了

84 578 657 802 148 566 360 817 045 728 307 604 764 590 139 606 051

和

97 823 979 291 139 750 018 446 800 724 120 182 692 777 022 032 973

这两个数，把它们相乘就可验证乘积等于上面的

8 273 820 869 309 776 799 973 961 823 304 474 636 656 020 157 784 206 028 082 108 433 763 964 611 304 313 040 029 095 633 352 319 623

计算机科学家认为因数分解不属于P类问题，也觉得它不是NP完全问题。它是很难，但不像可满足性问题或地图填色问题那样难。

不只是喜欢摆弄数字的数学家们认为质数判定和因数分解问题很重要。现代密码学的许多方法都依赖于某些难以分解因数的大数，这是第8章的话题。