先看下面这个数 Q, 它有 174  位数字:

18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

 现在告诉你, 它是两个大质数 P1 和 P2 相乘得到的, 问这两个质数是什么? 

答案:

P1 = 39807508642406493739712550055038649119906436234252
6708406385189575946388957261768583317

P2 = 47277214610743530253622307197304822463291469530209
7116459852171130520711256363590397527

上面的 Q = P1 X P2 是迄今为止已知的最大的用通用算法分解的大数，上述分解结果是由的德国的 J. Franke 和 T. Kleinjung 在 2003 年12月 3 号得到的, 他们因此获得了rsa security 悬赏的 $10,000 奖金. 更多的 " RSA 挑战数字(RSA challenge numbes) " 可以从 http://www.rsasecurity.com/rsalabs/node.asp?id=2093#RSA576 找到，解开其中任何一个都可以让你名利双收，最便宜的 rsa-640  也值 $20,000。

这样的问题称为大数分解(factoring)问题。大数分解对于加密的可靠性非常重要，如果你可以找到一个分解大数的快速算法，那么你就可以轻而易举地破解现在的基于  RSA 算法 的加密系统。

任意给两个大质数，我们可以很容易地算出它们的乘积。但反过来，给出该乘积，求它的分解却非常难。人们把这样的函数称为“单向函数(one-way function)”。但现在还没有人能够从理论上证明单向函数的存在。

大数分解显然是属于 NP(Nondeterministic Polynomial，非决定型多项式的) 的。但迄今为止，我们还不知道它是否属于 P(deterministic Polynomial，决定型多项式的)，还没有人发现大数分解的多项式算法。数学家们怀疑，大数分解根本上不存在一个通用的多项式算法，但这一点也没有得到证明。

Peter Shor 给出了一个能在量子计算机(quantum computer)上进行大数分解的多项式算法，Shor's algorithm。但目前为止它还只是于理论上存在，实际中人们还不知道如何构造一台量子计算机。

Shor 和他太太曾经写过以下小诗：

If computers that you build are quantum,
Then spies of all factions will want 'em.
Our codes will all fail,
And they'll read our email,
Till we've crypto that's quantum, and daunt 'em.

就在两星期前，2005 年 2 月 18 号，从德国传来一个好消息：Dr. Martin Nowak 发现了迄今为止已知的最大质数，2^25,964,951-1，即 2 的 25,964,951 次方减一。它一共有  7,816,230 位。

Dr. Martin Nowak 是住在德国 Michelfeld 的 一名眼科医生和业余数学爱好者。这个结果是他在一台 2.4 GHz Pentium 4 计算机上花了 50 天时间的运算得到的。法国的

Tony Reix 用 5 天时间在一台有 16个 CPU 的机器上验证了这一结果，他使用的验证程序是西班牙的 Guillermo Ballester Valor 所提供的 Glucas 。

这个迄今为止已知的最大质数也是第 42 个梅森质数(Mersenne Prime)。能够写成 "2 的 n 次方减一" 这样的形式的质数被称为梅森质数。梅森(1588-1648)是法国的一名传教士，他曾经专门研究过这样的质数。前四个梅森质数分别是 3，7，31，127。

1976 年，第 23 个梅森质数, 2^11213-1, 在 Illinois 大学数学系被发现，他们的系主任是如此的骄傲，以至于他决定把数学系寄出的所有信件上都盖上了 "2^11213-1 是质数" 这样的邮戳, 如下图所示.

发现一个梅森质数基本上可以使你名垂青史，如果你同时还想发点小财，注意这里：

Electronic Frontier Foundation 悬赏10 万美金 给首先发现位数超过 1 千万的梅森质数的人。 美国米西根的 Nayan Hajratwala  曾经在 2000 年因为发现了第 38 个梅森质数 2^6972593-1 （大约 2 百万位）而赢得 $50, 000 美元奖金。

欣赏一条数学定理及其巧妙证明所带来的精神上的审美快感可以和任何食色活动带来的快感相提并论,，至少在其持续的时间上可以这么说，如果不是在强度上的话。下面给出"有无穷多个质数" 的另一个证明。

定理  有无穷多个质数

证明：我们只需证明对任意一个给定的质数 N，总存在一个比它更大的质数。现在考察  N! + 1 = 1 x 2 X ... X N + 1。它或者是一个质数，或者不是。如果它是质数，那么我们已经找到一个比 N 大的质数，因为 N! + 1 > N。如果它不是质数，那么它一定可以被某个质数整除，设之为 Q。Q 不可能是从 1 到 N 的任何一个数，因为否则的话 (N! + 1 )/Q 余数为 1 。因此  Q 是一个大于 N 的质数。因此，无论 N! + 1 怎样，我们都将得到一个大于 N 的质数。所以对任意一个给定的质数 N，总存在一个比它更大的质数，也就是说不存在最大的质数，即有无穷多个质数。命题得证。

注意上面证明中用到了如下命题：如果正整数 M >1 不是质数，那么它一定能够被某个质数 P 整除，1 < P < M。这可以从质数的定义推出。

        数是美的。在所有数中，质数(prime number)最具一种神秘的美感，因为它最简单，质朴，仿佛来自宇宙最深处的某个神圣地方。

定义：质数(或素数)是大于一的整数，且不能被 1 和它本身之外的其它正整数整除。

An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.

前 10 个质数: 2, 3, 5, 7, 11, 13, 17, 19, 23, 19

前 10,000 个质数: http://www.utm.edu/research/primes/lists/small/10000.txt

一个拉出质数的小熊(prime number shitting bear): http://members.surfeu.fi/kklaine/primebear.html

质数的重要性在于任意自然数都可以分解为质数的乘积形式。从这个意义上说，质数是数的基本构造模块。例如：10 = 2 X 5，24 = 2 X 2 X 3。

 

古希腊人在大约公元前300年左右，也就是在我们战国七雄征战正酣的年代，就开始研究质数，发现了一些有趣的性质。例如，存在无穷多个质数，以及连续两个质数之间的距离可以是任意大。 欧几里得（Euclid）最早证明了存在无穷多个质数。下面我们看一个巧妙的证明。

定理 有无穷多个质数.

证明：假设只有有限多(r 个)质数，它们是 p1=2 < p2 = 3 < ... < pr . 令 P = p1p2...pr+1,  则 P 不是质数，所以它一定可以被某个质数整除。设 p  是整除 P 的一个质数，显然 p  不可能是  p1, p2, ..., pr 中的任意一个，否则 P  除以 p  的余数将为 1 。但这与假设 p1, p2, ..., pr 包括了所有的质数相矛盾。因此，假设不成立。命题得证。

 

另一个有趣的定理是不大于 x 的质数大约有 x/log x 个。因此，第 n 个质数的大小大约是 n logn。

 

最快的生成小质数(<10,000,000,000)的算法是Sieve of Eratosthenes 算法(公元前200年)。长期以来，人们一直不能确定质数判定这一问题是否存在多项式算法。出乎意料的是，在 2002 年，印度的 Agrawal, Kayal and Saxena 给出了一个质数判定的理论上的 有效算法 AKS 。 但这个算法在实际中还没有一个令人满意的有效实现。

 

关于质数有很多有趣的猜想, 其中最有名的一个是歌德巴赫猜想, 即著名的“ 1 + 1”：每个大于 2 的偶数都可以写成是两个质数的和。我国的非常牛的数学家陈景润（1966）证明了“1+2”，即每个大于 2 的偶数都可以写成一个质数和最多两个质数乘积的和。这是迄今为止的最好结果。