数学实验之五素数专题知识市公开课一等奖百校联赛特等奖课件.pptx

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