数学实验之五---素数课件

1、数学实验之五 - 素数中国科学技术大学数学系陈发来实验内容素数的个数素数表的构造素数的判别最大的素数求解素数的公式素数的分布1、素数的个数算术基本定理：任何整数都可以分解为设 为所有的素数。考察 如果N为合数，则N必以某些 为因子。这是不可能的！ 虽然素数有无穷多个，但随着整数范围越来越大，素数似乎越来越稀少。 1，100-25 1000,1100-16 100000, 100100-6 10000000,10000100-22、素数表的构造Eratosthenes筛法 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2

2、5 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),计算量

3、太大。Fermat判别法 如果p是素数，a与p互素，那么实际上，大约2500年前，中国古代数学家就发现了上述结论。他们由此得出：如果 ,则n为素数。该判别法的运算量为O(log3n). 通过编程计算发现，反过来结论并不成立。例如，但是341=11x34为合数！称使得成立的p为伪素数。注意同余的计算：进一步，伪素数有多少个？ 答案是无穷多个。实际上，数学家迈罗在1903年证明，如果n为伪素数，那么2n-1也是伪素数。 不过，同素数个数相比，伪素数的个数非常少。例如，在2x1010之内，伪素数不到素数的百万分之三。因此，可以认为 Fermat定理的逆定理几乎成立。利用伪素数表，可以给出判别素数的新

4、方法：如果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年，缪内发现了素性判别与黎曼猜想之

5、间的一个深刻联系。他的结论是： 在广义黎曼假设下，存在常数C, 对任何整数n, 若n为合数，则存在aC(logn)2 使得维路于1978年指出，上述常数C=70.由此可以设计如下多项式算法： 对任意n, 依次对a=1,2,70(logn)2检验上式是否成立。若对每一个a都不成立，则n为素数。否则，n 为合数。 上述算法的运算量为O(logn)5.年数学家Adleman, Rumely, Cohen和Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个位数的素性只需秒，对一个位数，只要秒，而一个位数只用秒。如果用试除法，判别一个位数的素性要一百亿年！概率判别法Lehmann:

6、给定p, 判断它是否为素数：（）选择一个小于p的随机数a;（）如果a与p不互素，则p为合数；（）计算 J=a(p-1) mod p；（）如果 J1或-1, 那么p为合数；（）如果 J=1或-1,那么p不是素数的可能性最多是50%.重复k次实验，那么p不是素数的可能性不超过1/2k.利用上述算法可以产生大的随机素数：（1）产生随机数p;（2）确保p不被较小的素数整除。（3）产生随机数a, 利用上述算法检测p的素性。直到经过多次测试为止。素性判别的多项式算法给定一个n位的整数，假设某一算法能在f(n)步内判断出该整数是否素数。如果f(n)是一个多项式的话，则称该算法具有多项式复杂性，称该问题是“多

7、项式可解的”。如果不存在一个算法其具有多项式的计算复杂性，则称该问题属于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是合数。

8、 1644年Mersenne宣称，对n=2,3,5,13, 17,19,31,67,127,257, M_n都是素数，而且对其它n257, M_n都是合数。 然而，后人证明M_67, M_257不是素数，而M_61, M_89, M_107都是素数。截止2002年2月, 数学家仅发现了39个 Mersenne素数. n 位数 时间86143259621982110503332651983132049397511983216091650501985 n 位数 时间756839 227832199285943325871619941257787378632199613982694209211996

9、29762218959321997302137790952619986972593209896019991346691740539452002Mersenne数素性的判别方法 定义数列u_0=4, u_k+1= u_k2-2 (mod M_n), k=1,2,., n. 如果u_n-1 =0(mod M_n), 则M_n为素数. 否则, M_n 为合数. 关于Mersenne素数的进一步问题： （1）Mersenne素数是否有无穷多个？ （2）对什么样的n,M_n是素数？是否存在求n的公式？至少使M_n为素数的n应该具有什么性质？ （3）如果M_n是合数，如果分解M_n？5、生成素数的公式是否

10、存在单变量整系数的多项式, 它只生成素数并且生成所有的素数? 更一般地,是否存在一个生成素数的多变量函数公式? 如果这样的公式不存在, 能否找到一个虽不能给出全部但能给出无穷多个素数(且只给出素数)的公式?Fermat数 形如F_n=22n+1的数被称为 Fermat数。 Fermat宣称，对所有的整数n, F_n永远是素数。 的确, F_0=3, F_1=5, F_2=17, F_3=257, F_4=65537都是素数。 但Euler指出F_5=4294967297=6416700417 是合数。后人验证出F_n (n4)都是合数。Fermat数F_n与正多边形做图有紧密的联系. 古代数学

11、家认为，当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合数是

12、否有无穷多个？（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), 其正值构成的集合恰好是素数的全体. 遗憾的是, 他并没有给出怎样具体地构造这样的多项式.

13、后经众多数学家的努力, 终于在1977年构造出了一个具有26个变量25次的素数生成多项式! 6、素数的分布素数沿数轴的分布 （1）随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？（2）相邻素数之间的间隔值有哪些? 它们各重复多少次? 哪些间隔值的重复次数多? 最大间隔值是多少? 随整数范围扩大, 最大间隔值是否也随之增大?（3）间隔差为2的素数对是否有无穷多个? 更一般地, 间隔差为某一个固定偶数的素数对是否有无穷多个? 是否存在相邻的素数, 其间隔值可以任意大?用(n)表示不超过n的素数的个数, (m,n)表示区间m,n内素数的个数. 固定d,绘制点列（i, (3i,3i

14、+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 猜想

15、导出的：这里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的

16、奇数可以表为三个奇素数之和. Euler在随后的复信中写道: 任何不小于6的偶数都是两个奇素数之和, 虽然我不能证明它, 但我确信无疑这是完全正确的定理. 这就是著名的Goldbach猜想的由来. 两百多年来, 无数数学家花费了大量的心血都未能解决这一问题.目前，有人验证到1014,命题仍然正确。1900年，Hilbert在巴黎世界数学家大会上提出23个问题供20世纪数学家研究。其中第8问题中将Goldbach猜想作为最重要的问题之一提出。1912年，在第五届世界数学家大会上，数学家兰道指出，即使证明下面较弱的命题，也是现代数学所力不能及的。任何整数都可以表示为不超过C个素数之和。1921年英

17、国数学家Hardy在哥本哈根召开的数学会议上说，Goldbach猜想的困难程度可以跟任何没解决的数学问题想比1930年，苏联数学家什尼尔列曼证明，任意整数都可以表为不超过k个素数之和,且k800000.1935年， k=2208 （苏联，罗曼诺夫）1936年，k=71 (德国，海尔布伦）1937年，k=67（意大利，里奇）1950年，k=20（美国，夏彼得）1956年，k=18（中国，尹文霖）1976年，k=6 (旺格汉）1937，苏联人维诺格拉夫证明，充分大的奇数可以表为三个素数的和。另一条路线：将大偶数表示为s个素数之积加上t个素数之和。记为“s+t”.年份证明者国家结果1920布龙挪威9

18、+91924拉特马赫德国7+71938布赫夕太勃苏联5+5; 4+41948兰恩尼匈牙利1+C1956王元中国3+4；3+31962潘乘洞中国1+51962王元中国1+41965布赫夕太勃苏联1+31966陈景润中国1+2Fermat大定理 设n是大于2的整数，则方程 无不存在非平凡的整数解。 Fermat 本人证明了n=4的情形。1753年，Euler证明了n=3.1825年，Dirchlet与Legendre证明了n=5.1832年，法国女数学家索非热尔曼证明：如果n和2n+1为素数，Fermat大定理成立。1839年，拉梅证明了n=7.1847年，德国数学家Kummer证明了对n2, 方

19、程只有有限个解。1993年，Princeton大学的教授威尔斯宣布证明了Fermat定理。但数学家发现了证明中的一个漏洞。经过九个月的努力威尔斯修正了这一错误，这标志着Fermat大定理被彻底征服。威尔斯的证明完全采用了全新的路线，用到了现代数学的许多分支：椭圆曲线论，模形式论，伽罗华表示论等。所谓椭圆曲线是如下形式的曲线：椭圆曲线与模形式之间有紧密的联系。50年代，日本数学家谷山丰和志村五郎猜测：有理数域上的每条椭圆曲线都存在模形式。被乘为“谷山-志村”猜想。60年代，有人将Femat 方程与椭圆曲线联系起来。1984年，佛赖证明，如果Fermat大定理不成，则由Fermat方程确定的椭圆曲

20、线不可能是模形式，这与谷山-志村猜想矛盾！因此，要证明Fermat大定理，只需证明谷山-志村猜想。威尔斯所做的正是证明了该猜想。大整数的素因子分解 正如判断一个大数的素性一样, 将一个大整数分解为素因子的乘积是一件相当艰难的事情, 迄今尚无一种通用有效的方法(试除法显然是不用考虑的). 目前，最有效的素因子分解方法的运算量大约为 O(exp(cL(1/3)log(L)(2/3), 其中L为要分解的整数N的位数。 利用现有大型计算机的能力, 能够分解的最大整数不能超过100位. 例如, 至今尚无人能分解Fermat数F_9. 读者能否给出F_6的分解?1994年，美国数学家Peter Shor做

21、出了一项惊人的工作。他指出，如果使用量子计算机，则因子分解算法的运算量为 O(L2log(L)loglog(L).完全数 所谓完全数是指它的所有因子(除去它本身 ) 之和等于该完全数. 例如, 6是一个完全数. 因为1+2+3=6. 下一个完全数是28. 请读者找出10000以内的所有完全数, 并对它做素因子分解. 你能据此猜测完全数的通式吗? 完全数与Mersenne素数有何联系? 你能由此找到更多的完全数吗? 是否存在奇完全数? 完全数是否有无穷多个?除6以外, 完全数都有一个奇妙的特性, 就是每个完全数可以表为几个连续的奇数之立方和. 如28=13+23. 请你对你找出的完全数验证此特性.完全数的另一个特性是它的因子的倒数和为1。如 1/2+1/3+1/6=1。把完全数（除6）各位数相加得另一数，这样一直做下去，最后得1。完全数二进制形式为：111000孪生素数