趣的一个问题是“是否有一个简单的方法或公式来产生素 数?”不幸的是,许多数学家的推测公式都是错误的,如 中国古代数学家曾提出下列测试法,以测试一个整数n 是否为素数。若n|2-2,则n为素数。事实上,对于所 有小于341的素数,上述测试法都成立。 2.梅森素数形如 M=22-1(p为素数) 的整数为素数者称为梅森( Mersenne)素数。至今只发现27 个,即 p=2,3,5,7,13,17,19,31,6189,107,1275212607,1279,2203,2281 3217,4253,4423,9689,99411213,21701,23209,44497 是否有无穷个梅森素数还未证明。M,=2047=23×89不 是素数。 费马素数形如 F=2+1(n为自然数) 的整数为素数者称为费马( Fermat)素数。至今只发现5个 费马素数 尽管如此,迄今为止仍然没有发现素数的模型或产生素数的 有效公式,因而寻找大的素数必须借助计算机一个一个地 找。用计算机算两个512位(二进制)的素数的乘积是一件 很容易的事情,但是如果给定一个1024位的数N,让你找出趣的一个问题是“是否有一个简单的方法或公式来产生素 数？”不幸的是，许多数学家的推测公式都是错误的，如： 1． 中国古代数学家曾提出下列测试法，以测试一个整数 n 是否为素数。若 | 2 − 2 n n ，则 n 为素数。事实上，对于所 有小于 341 的素数，上述测试法都成立。 2．梅森素数 形如 = 2 −1 p M p （ p 为素数） 的整数为素数者称为梅森（Mersenne）素数。至今只发现 27 个，即 3217,4253,4423,9689,9941,11213,21701,23209,44497 p = 2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281, 是否有无穷个梅森素数还未证明。 M11 = 2047 = 2389 不 是素数。 3．费马素数 形如 2 1 2 = + n F n （ n 为自然数） 的整数为素数者称为费马（Fermat）素数。至今只发现 5 个 费马素数 尽管如此，迄今为止仍然没有发现素数的模型或产生素数的 有效公式，因而寻找大的素数必须借助计算机一个一个地 找。用计算机算两个 512 位（二进制）的素数的乘积是一件 很容易的事情，但是如果给定一个 1024 位的数 N ，让你找出