资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数学试验之五,-,素数,中国科学技术大学数学系,陈发来,1/78,试验内容,素数个数,素数表结构,素数判别,最大素数,求解素数公式,素数分布,2/78,1、素数个数,算术基本定理：任何整数都能够分解为,设 为全部素数。考查,3/78,假如,N,为合数，则,N,必以一些 为因子。这是不可能！,即使素数有没有穷多个，但伴随整数范围越来越大，素数似乎越来越稀少。,1,，,100-25,1000,1100-16,100000,100100-6,10000000,10000100-2,4/78,2、素数表结构,Eratosthenes,筛法,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,于 19编织出了10000000以内素数表。,5/78,试除法,假设我们已经找到了前,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。,6/78,3、素数判别,威尔逊判别法,n,是素数充要条件是,这里,是指,a-b,被,p,整除。,不过该算法运算量为,O(nlogn2),计算量太大。,7/78,Fermat判别法,假如p是素数，a与p互素，那么,实际上，大约25前，中国古代数学家,就发觉了上述结论。他们由此得出：如,果 ,则n为素数。该判别法,运算量为O(log3n).,8/78,经过编程计算发觉，反过来结论并不成,立。比如，,不过,341=11x34,为合数！称使得,成立,p,为伪素数。,9/78,注意同余计算：,深入，伪素数有多少个？,10/78,答案是无穷多个。实际上，数学家迈罗在19证实，假如n为伪素数，那么2n-1也是伪素数。,不过，同素数个数相比，伪素数个数非常少。比如，在2x1010之内，伪素数不到素数百万分之三。所以，能够认为 Fermat定理逆定理几乎成立。,11/78,利用伪素数表，能够给出判别素数新方法：假如,p,不整除,2n-1,则,p,为合数；假如,p,整除,2n-1,且在伪素数表中，则,p,为合数，不然，,p,是素数。,伪素数能够推广到,a-,伪素数。令人惊奇是，存在这么数,p,它对任何,a,都是伪素数。比如，,561=3x11x17,就是这么一个伪素数，即,12/78,这么数称为绝对伪素数，也称迈克尔数。假如迈克尔数只有有限个，则对,nM,素数判别变得比较轻易。但迈克尔可能有没有限个，这使得直接用,Fermat,定理判别素性变得困难。,13/78,n-1,检验法,假设,n-1=FR,FR,gcd(F,R)=1.,假如对,F,每一个素因子,q,都存在一个整数,a1,满足,则,n,是素数。,14/78,基于广义黎曼猜测判别,1976,年，缪内发觉了素性判别与黎曼猜测之间一个深刻联络。他结论是：,在广义黎曼假设下，存在常数,C,对任何整数,n,若,n,为合数，则存在,aC(logn)2,使得,15/78,维路于,1978,年指出，上述常数,C=70.,由此能够设计以下多项式算法：,对任意,n,依次对,a=1,2,70(logn)2,检验上式是否成立。若对每一个,a,都不成立，则,n,为素数。不然，,n,为合数。,上述算法运算量为,O(logn)5.,16/78,年数学家,Adleman,Rumely,Cohen,和,Lenstra,研究出一个非常复杂、含有高度技巧素数判别方法，检验一个位数素性只需秒，对一个位数，只要秒，而一个位数只用秒。假如用试除法，判别一个位数素性要一百亿年！,17/78,概率判别法,Lehmann:,给定,p,判断它是否为素数：,（）选择一个小于,p,随机数,a;,（）假如,a,与,p,不互素，则,p,为合数；,（）计算,J=a(p-1)mod p,；,（）假如,J1,或,-1,那么,p,为合数；,（）假如,J=1,或,-1,那么,p,不是素数可能性最多是,50%.,18/78,重复,k,次试验，那么,p,不是素数可能性不超出,1/2k.,利用上述算法能够产生大随机素数：,（,1,）产生随机数,p;,（,2,）确保,p,不被较小素数整除。,（,3,）产生随机数,a,利用上述算法检测,p,素性。直到经过屡次测试为止。,19/78,素性判别多项式算法,给定一个,n,位整数，假设某一算法能在,f(n),步内判断出该整数是否素数。假如,f(n),是一个多项式话，则称该算法含有多项式复杂性，称该问题是“多项式可解”。假如不存在一个算法其含有多项式计算复杂性，则称该问题属于,NP,问题。,20/78,8月，印度理工大学计算机系三位学者提出了整数素性判别多项式算法！即素性判别问题是P类问题。他们指出算法复杂性普通为O(n12)。假如提供一些启发线索话，算法复杂性能够降到O(n6)甚至O(n3).,一个令人关注问题是，该算法是否会威胁现有RSA公钥密码体系安全？,21/78,4、最大素数,Mersenne,数,形如 数称为,Mersenne,数。利用,Mersenne,数能够结构出非常大素数。,很显然，假如,n,是合数，则,M_n,也为合数，但,n,为素数时，,M_n,不一定为素数。比如，,M_11=2047=23x89,是合数。,22/78,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,都是素数。,23/78,截止2月,数学家仅发觉了39个 Mersenne素数.,n,位数,时间,86143,25962,1982,110503,33265,1983,132049,39751,1983,216091,65050,1985,24/78,n,位数,时间,756839,227832,1992,859433,258716,1994,1257787,378632,1996,1398269,420921,1996,2976221,895932,1997,3021377,909526,1998,6972593,2098960,1999,13466917,4053945,25/78,Mersenne,数素性判别方法,定义数列,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,为合数,.,26/78,关于,Mersenne,素数深入问题,：,（,1,）,Mersenne,素数是否有没有穷多个？,（,2,）对什么样,n,M_n,是素数？是否存在求,n,公式？最少使,M_n,为素数,n,应该含有什么性质？,（,3,）假如,M_n,是合数，假如分解,M_n,？,27/78,5、生成素数公式,是否存在单变量整系数多项式,它只生成素数而且生成全部素数?,更普通地,是否存在一个生成素数多变量函数公式?,假如这么公式不存在,能否找到一个虽不能给出全部但能给出无穷多个素数(且只给出素数)公式?,28/78,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=641,6700417 是合数。,29/78,后人验证出,F_n(n4),都是合数。,Fermat,数,F_n,与正多边形做图有紧密联络.古代数学家认为，当,n,为大于,6,素数时，正,n,边形不能用圆规与直尺做出。不过，在,1796,年，,19,岁德国数学家,Gauss,找到了用直尺与圆规做正,17,边形方法。这一辉煌结果轰动了整个数学界。,30/78,五年后他深入证实了:一个正,n,边行可用直尺与园规作图充要条件是,n=2k,或者,n=2k p_1 p_2.p_r,其中,p_1,p_2,.,p_r,为不一样,Fermat,数.尤其地,正17边形能够用直尺与园规做出,.,今后，数学家梨西罗与盖尔美斯给出了正,257,边形与正,65537,边形做图法！,31/78,关于,Fermat,数主要研究问题是：,（,1,）怎样分解,Fermat,数？,（,2,）,Fermat,素数是否只有有限个？,（,3,）,Fermat,合数是否有没有穷多个？,（,4,）,Fermat,数有没有平方因子？,32/78,Euler,素数生成公式,Euler,曾研究过公式：,f(n)=n2+n+41.,能够验证，当,n=0,1,39,时，,f(n),都是 素数，但,f(40),是合数。有趣是，公式能给出相当多素数。,33/78,公式,n2+n+41,有一个非常奇特性质.为揭示这一特征,我们考查它二次求根公式判别式,d=12-4,1,41=-163.,163,有什么尤其地方？有!请看,34/78,作为,Hilbert,第十问题一个推论,马蒂雅舍维奇证实了:存在一个多元多项式,P(x_1,x_2,.,x_n),其正值组成集合恰好是素数全体.遗憾是,他并没有给出怎样详细地结构这么多项式.后经众多数学家努力,终于在1977年结构出了一个含有26个变量25次素数生成多项式!,35/78,6、素数分布,素数沿,数轴分布,（,1,）伴随整数范围扩大，素数是不是越来越稀疏？稀疏程度是否单调地增加？,（,2,）相邻素数之间间隔值有哪些?它们各重复多少次?哪些间隔值重复次数多?最大间隔值是多少?随整数范围扩大,最大间隔值是否也随之增大?,36/78,（,3,）间隔差为2素数对是否有没有穷多个?更普通地,间隔差为某一个固定偶数素数对是否有没有穷多个?是否存在相邻素数,其间隔值能够任意大?,37/78,用,(,n),表示不超出,n,素数个数,(,m,n),表示区间,m,n,内素数个数.,固定,d,绘制点列（,i,(,3,i,3i+d),i=1,2,N.,38/78,39/78,40/78,将素数从小到大次序排列,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),标在平面坐标系中.,41/78,42/78,43/78,44/78,45/78,素数个数,在二维坐标平面上标出点列(,n,(n),n=1,2,.,N(,取不一样,N,如1000,10000等).也能够用折线将点列连接起来.观察,(,n),趋于无穷趋势,.,46/78,47/78,48/78,49/78,50/78,由此猜测,关于素数个数近似公式首先是,Gauss,于,1792年给出,但他当初没能给出证实,.,勒让德也曾给出,51/78,以后，,Gauss,还给出了近似公式：,最靠近公式是由,Rieman,猜测导出：,这里,52/78,1852,年，俄国数学家切比雪夫证实了,这里,a=0.92,b=1.055.1892,年，英国数,学家希尔维斯特改进切比雪夫结果，得,到,a=0.956,b=1.044.,1896,Hadamard,与,Poussin,利用复变函数,理论加以证实.,53/78,素数定理初等证实于,1949,年著名数学家,Erdos,取得。,Riemann,猜测与素数分布有紧密联络。不过,Riemann,猜测至今仍未被证实,它无疑是数学上最著名难题之一。,54/78,7、深入思索问题,Goldbach,猜测,Goldbach,于1742年给大数学家,Euler,信中提出了两个猜测,即每个大于6偶数都能够表为两个奇素数之和;每个大于9奇数能够表为三个奇素数之和.,Euler,在随即复信中写道:任何大于6偶数都是两个奇素数之和,即使我不能证实它,但我确信无疑这是完全正确定理.这就是著名,Goldbach,猜测由来.,55/78,两百多年来,无数数学家花费了大量心血都未能处理这一问题.当前，有些人验证到1014,命题依然正确。,19，Hilbert在巴黎世界数学家大会上提出23个问题供20世纪数学家研究。其中第8问题中将Goldbach猜测作为最主要问题之一提出。,56/78,19，在第五届世界数学家大会上，数学家兰道指出，即使证实下面较弱命题，也是当代数学所力不能及。,任何整数都能够表示为不超出C个素数之和。,19英国数学家Hardy在哥本哈根召开数学会议上说，Goldbach猜测困难程度能够跟任何没处理数学问题想比,57/78,1930,年，苏联数学家什尼尔列曼证实，任意整数都能够表为不超出,k,个素数之和,且,k800000.,1935,年，,k=2208,（苏联，罗曼诺夫）,1936,年，,k=71(,德国，海尔布伦）,1937,年，,k=67,（意大利，里奇）,1950,年，,k=20,（美国，夏彼得）,58/78,1956,年，,k=18,（中国，尹文霖）,1976,年，,k=6(,旺格汉）,1937,，苏联人维诺格拉夫证实，充分大奇数能够表为三个素数和。,另一条路线：将大偶数表示为,s,个素数之积加上,t,个素数之和。记为“,s+t”.,59/78,年份,证实者,国家,结果,1920,布龙,挪威,9+9,1924,拉特马赫,德国,7+7,1938,布赫夕太勃,苏联,5+5;4+4,1948,兰恩尼,匈牙利,1+C,1956,王元,中国,3+4,；,3+3,1962,潘乘洞,中国,1+5,1962,王元,中国,1+4,1965,布赫夕太勃,苏联,1+3,1966,陈景润,中国,1+2,60/78,Fermat,大定理,设,n,是大于,2,整数，则方程,无不存在非平凡整数解。,61/78,Fermat,本人证实了,n=4,情形。,1753,年，,Euler,证实了,n=3.,1825,年，,Dirchlet,与,Legendre,证实了,n=5.,1832,年，法国女数学家索非热尔曼证实：假如,n,和,2n+1,为素数，,Fermat,大定理成立。,1839,年，拉梅证实了,n=7.,62/78,1847,年，德国数学家,Kummer,证实了对,n2,方程只有有限个解。,1993,年，,Princeton,大学教授威尔斯宣告证实了,Fermat,定理。但数学家发觉了证实中一个漏洞。经过九个月努力,63/78,威尔斯修正了这一错误，这标志着,Fermat,大定理被彻底征服。,威尔斯证实完全采取了全新路线，用到了当代数学许多分支：椭圆曲线论，模形式论，伽罗华表示论等。,所谓椭圆曲线是以下形式曲线：,64/78,椭圆曲线与模形式之间有紧密联络。,50,年代，日本数学家谷山丰和志村五郎猜测：有理数域上每条椭圆曲线都存在模形式。被乘为“谷山,-,志村”猜测。,60,年代,，有些人将,Femat,方程与椭圆曲线联络起来。,1984,年，佛赖证实，假如,Fermat,大定理不成，则由,Fermat,方程确定椭圆曲线不可能是模形式，这与,谷山,-,65/78,志村猜测矛盾！所以，要证实,Fermat,大定理，只需证实谷山,-,志村猜测。威尔斯所做正是证实了该猜测。,66/78,大整数素因子分解,正如判断一个大数素性一样,将一个大整数分解为素因子乘积是一件相当艰难事情,迄今尚无一个通用有效方法(试除法显然是不用考虑).当前，最有效素因子分解方法运算量大约为,O(exp(cL(1/3)log(L)(2/3),其中L为要分解整数N位数,。,67/78,利用现有大型计算机能力,能够分解最大整数不能超出100位.比如,至今尚无人能分解,Fermat,数,F_9.,读者能否给出,F_6,分解?,1994年，美国数学家,Peter Shor,做出了一项惊人工作。他指出，假如使用量子计算机，则因子分解算法运算量为,O(L2log(L)loglog(L).,68/78,完全数,所谓完全数是指它全部因子(除去它本身)之和等于该完全数.比如,6是一个完全数.因为1+2+3=6.下一个完全数是28.请读者找出10000以内全部完全数,并对它做素因子分解.你能据此猜测完全数通式吗?完全数与,Mersenne,素数有何联络?你能由此找到更多完全数吗?是否存在奇完全数?完全数是否有没有穷多个?,69/78,除6以外,完全数都有一个奇妙特征,就是每个完全数能够表为几个连续奇数之立方和.如28=13+23.请你对你找出完全数验证此特征.,完全数另一个特征是它因子倒数和为,1,。如,1/2+1/3+1/6=1,。,把完全数（除,6,）各位数相加得另一数，这么一直做下去，最终得,1,。,完全数二进制形式为：,111000,70/78,孪生素数,间隔为2相邻素数，如3与5，5与7。关于孪生素数猜测是：孪生素数有没有穷多个。,19，挪威数学家布隆考虑孪生素数倒数和：,71/78,假如上述数列发散，则孪生素数有没有穷多个。遗憾是，上述数列收敛，其和为,B=1.90216054.,用,p(x),表示不超出,x,孪生素数个数。英国数学家,Hardy,与,Littlewood,猜测,其中,72/78,迄今为止，孪生素数猜测还没有证实。当前最好结果是我国数学家陈景润于,1966,年取得：存在无穷多个素数,p,使,p+2,是不超出两个素数乘积。截止,1999,年发觉最大孪生素数是,73/78,青一色数素性,由,n,个1组成数11.,1,叫做青一色数.当,n,为何值时,青一色数是素数?假如青一色数是合数,怎样将它做素因子分解?,很显然，假如,n,为合数，则清一色数为合数。当前只好到,n=2,19,23,317,1031,时，清一色数为素数。,74/78,Bertrand,猜测,当,n3,时,n,与2,n-2,之间最少存在一个素数,.,1852,年，,俄国数学家切比雪夫证实该猜测。,深入，对怎样大,d0,n,与,(1+d)n,之间必定有素数呢？,1893,年法国数学家凯恩证实，对任意,d0,只要,n,足够大，上述结论成立。,75/78,继,Bertrand,猜测之后，,1882,年奥波曼提出新猜测：在,n2,和,n(n+1),之间必有素数。但现在还没有取得证实。当前最好结果是：,n2,与,n2+nk,之间有素数。这里,k12/11.,76/78,相关,Mathematica,函数,FactorIntegern,Modm,n,PrimeQn,Primen,ListPlotx1,y1,x2,y2,x_n,y_n,PlotJoined-True,Table,77/78,Thank you very muchfor your presence,78/78,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
