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

1、数学实验之五数学实验之五 -素数素数中国科学技术大学数学系陈发来1213466917实验内容实验内容l素数的个数l素数表的构造l素数的判别l最大的素数l求解素数的公式l素数的分布1 1、素数的个数、素数的个数 算术基本定理：任何整数都可以分解为 设 为所有的素数。考察nppp,21121npppNkdkddpppn2121 如果N为合数，则N必以某些 为因子。这是不可能的！虽然素数有无穷多个，但随着整数范围越来越大，素数似乎越来越稀少。1，100-25 1000,1100-16 100000,100100-6 10000000,10000100-2ip2 2、素数表的构造、素数表的构造 Era

2、tosthenesEratosthenes筛法筛法 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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.为提高算法的

3、效率，只需用不超过 的素数去除N。N3 3、素数的判别、素数的判别威尔逊判别法威尔逊判别法 n是素数的充要条件是 这里 是指 a-b 被p整除。不过该算法的运算量为O(nlogn2),计算量太大。pbamod)(mod01)!1(nn FermatFermat判别法判别法 如果p是素数，a与p互素，那么实际上，大约2500年前，中国古代数学家就发现了上述结论。他们由此得出：如果 ,则n为素数。该判别法的运算量为O(log3n).papmod11)2(mod22 n 通过编程计算发现，反过来结论并不成立。例如，但是341=11x34为合数！称使得成立的p为伪素数。341mod12340ppmod

4、121注意同余的计算：进一步，伪素数有多少个？341mod1)13413(1024)2(234343410340 答案是无穷多个。实际上，数学家迈罗在1903年证明，如果n为伪素数，那么2n-1也是伪素数。不过，同素数个数相比，伪素数的个数非常少。例如，在2x1010之内，伪素数不到素数的百万分之三。因此，可以认为 Fermat定理的逆定理几乎成立。利用伪素数表，可以给出判别素数的新方法：如果p不整除2n-1,则p为合数；如果p整除2n-1,且在伪素数表中，则p为合数，否则，p是素数。伪素数可以推广到a-伪素数。令人惊奇的是，存在这样的数p,它对任何a都是伪素数。例如，561=3x11x17就

5、是这样一个伪素数，即)561(mod1560a 这样的数称为绝对伪素数，也称迈克尔数。如果迈克尔数只有有限个，则对nM,素数的判别变得比较容易。但迈克尔可能有无限个，这使得直接用Fermat 定理判别素性变得困难。n-1检验法检验法 假设n-1=FR,FR,gcd(F,R)=1.如果对F的每一个素因子q都存在一个整数a1满足 则n是素数。1),1gcd(),(mod1/)1(1nanaqnn 基于广义黎曼猜想的判别基于广义黎曼猜想的判别 1976年，缪内发现了素性判别与黎曼猜想之间的一个深刻联系。他的结论是：在广义黎曼假设下，存在常数C,对任何整数n,若n为合数，则存在aC(logn)2 使得

6、)(mod21nnaan 维路于1978年指出，上述常数C=70.由此可以设计如下多项式算法：对任意n,依次对a=1,2,70(logn)2检验上式是否成立。若对每一个a都不成立，则n为素数。否则，n 为合数。上述算法的运算量为O(logn)5.年数学家Adleman,Rumely,Cohen和Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个位数的素性只需秒，对一个位数，只要秒，而一个位数只用秒。如果用试除法，判别一个位数的素性要一百亿年！概率判别法概率判别法 Lehmann:给定p,判断它是否为素数：（）选择一个小于p的随机数a;（）如果a与p不互素，则p为合数；（）计

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

8、002年8月，印度理工大学计算机系的三位学者提出了整数素性判别的多项式算法！即素性判别问题是P类问题。他们指出算法复杂性一般为O(n12)。如果提供某些启发线索的话，算法的复杂性可以降到O(n6)甚至O(n3).一个令人关注的问题是，该算法是否会威胁现有的RSA公钥密码体系的安全？4、最大的素数 MersenneMersenne数数 形如 的数称为Mersenne数。利用Mersenne数可以构造出非常大的素数。很显然，如果n是合数，则M_n也为合数，但n为素数时，M_n不一定为素数。例如，M_11=2047=23x89是合数。12 nnM 1644年Mersenne宣称，对n=2,3,5,1

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

10、9321997302137790952619986972593209896019991346691740539452002 MersenneMersenne数素性的判别方法数素性的判别方法 定义数列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 为合数.关于关于MersenneMersenne素数的进一步问题素数的进一步问题：（1）Mersenne素数是否有无穷多个？（2）对什么样的n,M_n是素数？是否存在求n的公式？至少使M_n为素数的n应该具有什么性质？（3）如果M_n是合数，如果分解M_n

11、？5、生成素数的公式 是否存在单变量整系数的多项式,它只生成素数并且生成所有的素数?更一般地,是否存在一个生成素数的多变量函数公式?如果这样的公式不存在,能否找到一个虽不能给出全部但能给出无穷多个素数(且只给出素数)的公式?FermatFermat数数 形如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与正多边形做图有紧密的联系

12、.古代数学家认为，当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合数是否有

13、无穷多个？（4）Fermat数有没有平方因子？EulerEuler素数生成公式素数生成公式 Euler曾研究过公式：f(n)=n2+n+41.可以验证，当n=0,1,39时，f(n)都是 素数，但f(40)是合数。有趣的是，公式能给出相当多的素数。公式n2+n+41有一个非常奇特的性质.为揭示这一特性,我们考察它的二次求根公式的判别式d=12-4141=-163.163有什么特别的地方？有!请看 0000000000040768744.02625374126163e 作为Hilbert第十问题的一个推论,马蒂雅舍维奇证明了:存在一个多元多项式P(x_1,x_2,.,x_n),其正值构成的集合恰

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

15、(m,n)表示区间m,n内素数的个数.固定d,绘制点列（i,(3i,3i+d),i=1,2,N.1020304050510152025100d10203040502550751001251501000d 将素数从小到大顺序排列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)标在平面坐标系中.5001000150020005101520255001000150020005101520255101520253035501001502002501000N510152025303550

16、010001500200010000N 素数的个数素数的个数 在二维坐标平面上标出点列(n,(n),n=1,2,.,N(取不同的N,如1000,10000等).也可以用折线将点列连接起来.观察(n)趋于无穷的趋势.200040006000800010000200400600800100012002000400060008000100005001000150020002000400060008000100005678)(/nn)log()(/nnn由此猜测关于素数个数的近似公式首先是Gauss 于1792年给出的,但他当时没能给出证明.勒让德也曾给出)log(/)(nnn)08366.1/(ln

17、)(xxx 后来，Gauss还给出了近似公式：最接近的公式是由Rieman 猜想导出的：这里xxdxx2log/1)(1!/)(log)1(/11)(kkknkkxR.3/12/11)(kkk 1852年，俄国数学家切比雪夫证明了这里a=0.92,b=1.055.1892年，英国数学家希尔维斯特改进切比雪夫的结果，得到a=0.956,b=1.044.1896,Hadamard与Poussin利用复变函数的理论加以证明.xxbxxxaln/)(ln/素数定理的初等证明于1949年著名数学家Erdos获得。Riemann猜想与素数的分布有紧密的联系。不过Riemann猜想至今仍未被证明,它无疑是数

18、学上最著名的难题之一。7、进一步的思考问题 GoldbachGoldbach 猜想猜想 Goldbach于1742年给大数学家Euler的信中提出了两个猜想,即每个不小于6的偶数都可以表为两个奇素数之和;每个不小于9的奇数可以表为三个奇素数之和.Euler在随后的复信中写道:任何不小于6的偶数都是两个奇素数之和,虽然我不能证明它,但我确信无疑这是完全正确的定理.这就是著名的Goldbach猜想的由来.两百多年来,无数数学家花费了大量的心血都未能解决这一问题.目前，有人验证到1014,命题仍然正确。1900年，Hilbert在巴黎世界数学家大会上提出23个问题供20世纪数学家研究。其中第8问题中

19、将Goldbach猜想作为最重要的问题之一提出。1912年，在第五届世界数学家大会上，数学家兰道指出，即使证明下面较弱的命题，也是现代数学所力不能及的。任何整数都可以表示为不超过任何整数都可以表示为不超过C个素数之个素数之和。和。1921年英国数学家Hardy在哥本哈根召开的数学会议上说，Goldbach猜想的困难程度可以跟任何没解决的数学问题想比 1930年，苏联数学家什尼尔列曼证明，任意整数都可以表为不超过k个素数之和,且k800000.1935年，k=2208（苏联，罗曼诺夫）1936年，k=71(德国，海尔布伦）1937年，k=67（意大利，里奇）1950年，k=20（美国，夏彼得）1

20、956年，k=18（中国，尹文霖）1976年，k=6(旺格汉）1937，苏联人维诺格拉夫证明，充分大的奇数可以表为三个素数的和。另一条路线：将大偶数表示为s个素数之积加上t个素数之和。记为“s+t”.年份证明者国家结果1920布龙挪威9+91924拉特马赫德国7+71938布赫夕太勃苏联5+5;4+41948兰恩尼匈牙利1+C1956王元中国3+4；3+31962潘乘洞中国1+51962王元中国1+41965布赫夕太勃苏联1+31966陈景润中国1+2 Fermat大定理大定理 设n是大于2的整数，则方程 无不存在非平凡的整数解。nnnzyx Fermat 本人证明了n=4的情形。1753年，

21、Euler证明了n=3.1825年，Dirchlet与Legendre证明了n=5.1832年，法国女数学家索非热尔曼证明：如果n和2n+1为素数，Fermat大定理成立。1839年，拉梅证明了n=7.1847年，德国数学家Kummer证明了对n2,方程只有有限个解。1993年，Princeton大学的教授威尔斯宣布证明了Fermat定理。但数学家发现了证明中的一个漏洞。经过九个月的努力 威尔斯修正了这一错误，这标志着Fermat大定理被彻底征服。威尔斯的证明完全采用了全新的路线，用到了现代数学的许多分支：椭圆曲线论，模形式论，伽罗华表示论等。所谓椭圆曲线是如下形式的曲线：dcxbxaxy23

22、2 椭圆曲线与模形式之间有紧密的联系。50年代，日本数学家谷山丰和志村五郎猜测：有理数域上的每条椭圆曲线都存在模形式。被乘为“谷山-志村”猜想。60年代，有人将Femat 方程与椭圆曲线联系起来。1984年，佛赖证明，如果Fermat大定理不成，则由Fermat方程确定的椭圆曲线不可能是模形式，这与谷山-志村猜想矛盾！因此，要证明Fermat大定理，只需证明谷山-志村猜想。威尔斯所做的正是证明了该猜想。大整数的素因子分解大整数的素因子分解 正如判断一个大数的素性一样,将一个大整数分解为素因子的乘积是一件相当艰难的事情,迄今尚无一种通用有效的方法(试除法显然是不用考虑的).目前，最有效的素因子分

23、解方法的运算量大约为 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+3=6.下一个完全数是28.请读者找出10000以内的所有完全数,并对它做素因子分解.你能据此猜测完全

24、数的通式吗?完全数与Mersenne素数有何联系?你能由此找到更多的完全数吗?是否存在奇完全数?完全数是否有无穷多个?除6以外,完全数都有一个奇妙的特性,就是每个完全数可以表为几个连续的奇数之立方和.如28=13+23.请你对你找出的完全数验证此特性.完全数的另一个特性是它的因子的倒数和为1。如 1/2+1/3+1/6=1。把完全数（除6）各位数相加得另一数，这样一直做下去，最后得1。完全数二进制形式为：111000 孪生素数孪生素数 间隔为2的相邻素数，如3与5，5与7。关于孪生素数的猜想是：孪生素数有无穷多个。1919年，挪威数学家布隆考虑孪生素数的倒数和：)7/15/1()5/13/1(

25、B 如果上述数列发散，则孪生素数有无穷多个。遗憾的是，上述数列收敛，其和为B=1.90216054.用p(x)表示不超过x的孪生素数的个数。英国数学家Hardy与Littlewood猜测 其中2)/(ln2)(xcxxp)6/11)(4/11)(2/11(222c 迄今为止，孪生素数猜想还没有证明。目前最好的结果是我国数学家陈景润于1966年获得：存在无穷多个素数p,使p+2是不超过两个素数的乘积。截止1999年发现的最大孪生素数是1236170005539020 青一色数的素性青一色数的素性 由n个1组成的数11.1叫做青一色数.当n为何值时,青一色数是素数?如果青一色数是合数,如何将它做素

26、因子分解?很显然，如果n为合数，则清一色数为合数。目前只得到n=2,19,23,317,1031时，清一色数为素数。BertrandBertrand猜测猜测 当n3时,n与2n-2之间至少存在一个素数.1852年，俄国数学家切比雪夫证明该猜想。进一步，对怎样大的d0,n与(1+d)n之间必然有素数呢？1893年法国数学家凯恩证明，对任意d0,只要n足够大，上述结论成立。继Bertrand猜想之后，1882年奥波曼提出新的猜想：在n2和n(n+1)之间必有素数。但现在还没有获得证明。目前的最好结果是：n2与n2+nk之间有素数。这里k12/11.相关的Mathematica函数 FactorIntegern Modm,n PrimeQn Primen ListPlotx1,y1,x2,y2,x_n,y_n PlotJoined-True TableThank you very muchfor your presence