数学实验之五 - 素数中国科学技术大学数学系陈发来实验内容l素数的个数 l素数表的构造 l素数的判别 l最大的素数 l求解素数的公式 l素数的分布1、素数的个数算术基本定理：任何整数都可以分解为设 为所有的素数。 考察如果N为合数，则N必以某些 为因子 。这是不可能的！虽然素数有无穷多个，但随着整数范围 越来越大，素数似乎越来越稀少。1，100-251000,1100-16100000, 100100-610000000,10000100-22、素数表的构造 Eratosthenes筛法2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1718 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 经过众多学者的艰辛努力, D.N.Lehmer 于 1914年编织出了10000000以内的素数表 。 试除法假设我们已经找到了前n个素数p_1=2, p_2=3, .,p_n, 为了寻找下一个素数我 们从p_n+2开始依次检验每一个整数N, 看 N是否能被某个p_i, i=1,2,.,n整除. 如果N能被前面的某个素数整除, 则N为合 数. 否则N即为下 一个素数p_n+1. 为提高算法的效率，只需用不超过 的素数去除N。3、素数的判别威尔逊判别法n是素数的充要条件是这里 是指 a-b 被p整 除。不过该算法的运算量为O(nlogn2),计 算量太大。Fermat判别法如果p是素数，a与p互素，那么实际上，大约2500年前，中国古代数学家 就发现了上述结论。他们由此得出：如 果 ,则n为素数。该判别法 的运算量为O(log3n).通过编程计算发现，反过来结论并不成 立。例如，但是341=11x34为合数！称使得成立的p为伪素数。注意同余的计算：进一步，伪素数有多少个？答案是无穷多个。实际上，数学家迈 罗在1903年证明，如果n为伪素数， 那么2n-1也是伪素数。不过，同素数个数相比，伪素数的个 数非常少。例如，在2x1010之内， 伪素数不到素数的百万分之三。因此 ，可以认为 Fermat定理的逆定理几乎 成立。 利用伪素数表，可以给出判别素数的新方 法：如果p不整除2n-1, 则p为合数；如果 p整除2n-1, 且在伪素数表中，则p为合数 ，否则，p是素数。 伪素数可以推广到a-伪素数。令人惊奇的 是，存在这样的数p, 它对任何a都是伪素 数。例如，561=3x11x17就是这样一个伪 素数，即 这样的数称为绝对伪素数，也称迈克尔 数。如果迈克尔数只有有限个，则对 nM, 素数的判别变得比较容易。但迈克 尔可能有无限个，这使得直接用Fermat 定理判别素性变得困难。 n-1检验法假设n-1=FR, FR, gcd(F,R)=1. 如果对F的 每一个素因子q都存在一个整数a1满足则n是素数。 基于广义黎曼猜想的判别1976年，缪内发现了素性判别与黎曼猜 想之间的一个深刻联系。他的结论是：在广义黎曼假设下，存在常数C, 对任何 整数n, 若n为合数，则存在a1或-1, 那么p为合数； （）如果 J=1或-1, 那么p不是素数 的可能性最多是50%. 重复k次实验，那么p不是素数的可能性 不超过1/2k. 利用上述算法可以产生大的随机素数： （1）产生随机数p; （2）确保p不被较小的素数整除。 （3）产生随机数a, 利用上述算法检测p 的素性。直到经过多次测试为止。 素性判别的多项式算法给定一个n位的整数，假设某一算法能在 f(n)步内判断出该整数是否素数。如果 f(n)是一个多项式的话，则称该算法具有 多项式复杂性，称该问题是“多项式可解 的”。如果不存在一个算法其具有多项式 的计算复杂性，则称该问题属于NP问题 。 2002年8月，印度理工大学计算机系的三 位学者提出了整数素性判别的多项式算 法！即素性判别问题是P类问题。他们指 出算法复杂性一般为O(n12)。如果提供 某些启发线索的话，算法的复杂性可以 降到O(n6)甚至O(n3). 一个令人关注的问题是，该算法是否会 威胁现有的RSA公钥密码体系的安全？4、最大的素数 Mersenne数形如 的数称为Mersenne数。 利用Mersenne数可以构造出非常大的素 数。很显然，如果n是合数，则M_n也为合数 ，但n为素数时，M_n不一定为素数。例 如，M_11=2047=23x89是合数。1644年Mersenne宣称，对n=2,3,5,13, 17,19,31,67,127,257, M_n都是素数， 而且对其它n4)都是合数。 Fermat数F_n与正多边形做图有紧密的联 系. 古代数学家认为，当n为大于6的素 数时，正n边形不能用圆规与直尺做出。 但是，在1796年，19岁的德国数学家 Gauss找到了用直尺与圆规做正17边形的 方法。这一辉煌的成果轰动了整个数学 界。 五年后他进一步证明了: 一个正n边行可 用直尺与园规作图的充要条件是, n=2k 或者n=2k p_1 p_2. p_r, 其中 p_1,p_2,.,p_r为不同的Fermat数. 特 别地, 正17边形可以用直尺与园规做出. 此后，数学家梨西罗与盖尔美斯给出了 正257边形与正65537边形的做图法！ 关于Fermat数主要研究的问题是： （1）如何分解Fermat数？ （2）Fermat素数是否只有有限个？ （3）Fermat合数是否有无穷多个？ （4）Fermat数有没有平方因子？ Euler素数生成公式Euler曾研究过公式：f(n)=n2+n+41. 可以验证，当n=0,1,39时，f(n)都是 素数，但f(40)是合数。有趣的是，公式 能给出相当多的素数。 公式n2+n+41有一个非常奇特的性质. 为揭示这一特性, 我们考察它的二次求 根公式的判别式d=12-4141 =- 163.163有什么特别的地方？有! 请看 作为Hilbert第十问题的一个推论, 马蒂 雅舍维奇证明了: 存在一个多元多项式 P(x_1,x_2,.,x_n), 其正值构成的集 合恰好是素数的全体. 遗憾的是, 他并 没有给出怎样具体地构造这样的多项式. 后经众多数学家的努力, 终于在1977年 构造出了一个具有26个变量25次的素数 生成多项式! 6、素数的分布 素数沿数轴的分布 （1）随着整数范围的扩大，素数是不是 越来越稀疏？稀疏的程度是否单调地增 加？ （2）相邻素数之间的间隔值有哪些? 它 们各重复多少次? 哪些间隔值的重复次 数多? 最大间隔值是多少? 随整数范围 扩大, 最大间隔值是否也随之增大? （3）间隔差为2的素数对是否有无穷多 个? 更一般地, 间隔差为某一个固定偶 数的素数对是否有无穷多个? 是否存在 相邻的素数, 其间隔值可以任意大? 用(n)表示不超过n的素数的个数, (m,n)表示区间m,n内素数的个数.固定d,绘制点列（i, (3i,3i+d), i=1,2,N. 将素数从小到大顺序排列p_1=2, p_2=3, ., 用d_n=p_n+1-p_n表示相邻素数间 的间隔. 计算d_1,d_2,., d_N(如 N=1000, 10000), 然后将点(p_n,d_n)标在 平面坐标系中. 素数的个数在二维坐标平面上标出点列(n, (n), n=1,2,., N(取不同的N, 如1000, 10000等). 也可以用折线将点列连接起 来. 观察(n)趋于无穷的趋势.由此猜测关于素数个数的近似公式首先是Gauss 于 1792年给出的,但他当时没能给出证明. 勒让德也曾给出后来，Gauss还给出了近似公式：最接近的公式是由Rieman 猜想导出的：这里 1852年，俄国数学家切比雪夫证明了这里a=0.92, b=1.055. 1892年，英国数 学家希尔维斯特改进切比雪夫的结果，得 到a=0.956, b=1.044. 1896,Hadamard与Poussin利用复变函数的 理论加以证明. 素数定理的初等证明于1949年著名数学家 Erdos获得。 Riemann猜想与素数的分布有紧密的联系 。不过Riemann猜想至今仍未被证明, 它 无疑是数学上最著名的难题之一。7、 进一步的思考问题 Goldbach 猜想Goldbach于1742年给大数学家Euler的 信中提出了两个猜想, 即每个不小于6的 偶数都可以表为两个奇素数之和; 每个不 小于9的奇数可以表为三个奇素数之和.Euler在随后的复信中写道: 任何不小于6 的偶数都是两个奇素数之和, 虽然我不能 证明它, 但我确信无疑这是完全正确的定 理. 这就是著名的Goldbach猜想的由来. 两百多年来, 无数数学家花费了大量的 心血都未能解决这一问题.目前，有人验 证到1014,命题仍然正确。 1900年，Hilbert在巴黎世界数学家大会 上提出23个问题供20世纪数学家研究。 其中第8问题中将Goldbach猜想作为最重 要的问题之一提出。 1912年，在第五届世界数学家大会上， 数学家兰道指出，即使证明下面较弱的 命题，也是现代数学所力不能及的。 任何整数都可以表示为不超过C个素数之 和。 1921年英国数学家Hardy在哥本哈根召开 的数学会议上说，Goldbach猜想的困难 程度可以跟任何没解决的数学问题想比 1930年，苏联数学家什尼尔列曼证明， 任意整数都可以表为不超过k个素数之和, 且k2, 方程只有有限个解。 1993年，Princeton大学的教授威尔斯宣 布证明了Fermat定理。但数学家发现了 证明中的一个漏洞。经过九个月的努力 威尔斯修正了这一错误，这标志着 Fermat大定理被彻底征服。 威尔斯的证明完全采用了全新的路线， 用到了现代数学的许多分支：椭圆曲线 论，模形式论，伽罗华表示论等。 所谓椭圆曲线是如下形式的曲线： 椭圆曲线与模形式之间有紧密的联系。 50年代，日本数学家谷山丰和志村五郎 猜测：有理数域上的每条椭圆曲线都存 在模形式。被乘为“谷山-志村”猜想。 60年代，有人将Femat 方程与椭圆曲线联 系起来。1984年，佛赖证明，如果 Fermat大定理不成，则由Fermat方程确定 的椭圆曲线不可能是模形式，这与谷山- 志村猜想矛盾！因此，要证明Fermat大 定理，只需证明谷山-志村猜想。威尔斯 所做的正是证明了该猜想。 大整数的素因子分解正如判断一个大数的素性一样, 将一个 大整数分解为素因子的乘积是一件相当 艰难的事情, 迄今尚无一种通用有效的 方法(试除法显然是不用考虑的). 目前 ，最有效的素因子分解方法的运算量大 约为 O(exp(cL(1/3)log(L)(2/3), 其中L为要分解的整数N的位数。 利用现有大型计算机的能力, 能够分解 的最大整数不能超过100位. 例如, 至今 尚无人能分解Fermat数F_9. 读者能否给 出F_6的分解? 1994年，美国数学家Peter Shor做出了 一项惊人的工作。他指出，如果使用量 子计算机，则因子分解算法的运算量为 O(L2log(L)loglog(L). 完全数 所谓完全数是指它的所有因子(除去它本身 ) 之和等于该完全数. 例如, 6是一个完全 数. 因为1+2+