数学实验之五 --- 素数中国科学技术大学数学系陈发来实验内容l素数的个数 l素数表的构造 l素数的判别 l最大的素数 l求解素数的公式 l素数的分布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 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}. 为提高算法的效率，只需用不超过 的素数去除N3、素数的判别威尔逊判别法n是素数的充要条件是这里 是指 a-b 被p整 除不过该算法的运算量为O(nlogn^2),计 算量太大Fermat判别法如果p是素数，a与p互素，那么实际上，大约2500年前，中国古代数学家 就发现了上述结论他们由此得出：如 果 ,则n为素数该判别法 的运算量为O(log^3n).通过编程计算发现，反过来结论并不成 立例如，但是341=11x34为合数！称使得成立的p为伪素数注意同余的计算：进一步，伪素数有多少个？答案是无穷多个实际上，数学家迈 罗在1903年证明，如果n为伪素数， 那么2^n-1也是伪素数不过，同素数个数相比，伪素数的个 数非常少。
例如，在2x10^10之内， 伪素数不到素数的百万分之三因此 ，可以认为 Fermat定理的逆定理几乎 成立• 利用伪素数表，可以给出判别素数的新方 法：如果p不整除2^n-1, 则p为合数；如果 p整除2^n-1, 且在伪素数表中，则p为合数 ，否则，p是素数 • 伪素数可以推广到a-伪素数令人惊奇的 是，存在这样的数p, 它对任何a都是伪素 数例如，561=3x11x17就是这样一个伪 素数，即• 这样的数称为绝对伪素数，也称迈克尔 数如果迈克尔数只有有限个，则对 n>M, 素数的判别变得比较容易但迈克 尔可能有无限个，这使得直接用Fermat 定理判别素性变得困难• n-1检验法假设n-1=FR, F>R, gcd(F,R)=1. 如果对F的 每一个素因子q都存在一个整数a>1满足则n是素数• 基于广义黎曼猜想的判别1976年，缪内发现了素性判别与黎曼猜 想之间的一个深刻联系他的结论是：在广义黎曼假设下，存在常数C, 对任何 整数n, 若n为合数，则存在a1或-1, 那么p为合数； • （５）如果 J=1或-1, 那么p不是素数 的可能性最多是50%.• 重复k次实验，那么p不是素数的可能性 不超过1/2^k.• 利用上述算法可以产生大的随机素数： • （1）产生随机数p; • （2）确保p不被较小的素数整除。
• （3）产生随机数a, 利用上述算法检测p 的素性直到经过多次测试为止• 素性判别的多项式算法给定一个n位的整数，假设某一算法能在 f(n)步内判断出该整数是否素数如果 f(n)是一个多项式的话，则称该算法具有 多项式复杂性，称该问题是“多项式可解 的”如果不存在一个算法其具有多项式 的计算复杂性，则称该问题属于NP问题 • 2002年8月，印度理工大学计算机系的三 位学者提出了整数素性判别的多项式算 法！即素性判别问题是P类问题他们指 出算法复杂性一般为O(n^12)如果提供 某些启发线索的话，算法的复杂性可以 降到O(n^6)甚至O(n^3).• 一个令人关注的问题是，该算法是否会 威胁现有的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=2^k 或者n=2^k 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)=n^2+n+41. 可以验证，当n=0,1,…,39时，f(n)都是 素数，但f(40)是合数有趣的是，公式 能给出相当多的素数• 公式n^2+n+41有一个非常奇特的性质. 为揭示这一特性, 我们考察它的二次求 根公式的判别式d=1^2-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, (3^i,3^i+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猜想的由来. • 两百多年来, 无数数学家花费了大量的 心血都未能解决这一问题.目前，有人验 证到10^14,命题仍然正确 • 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(L^2log(L)loglog(L)).• 完全数 所谓完全数是指它的所有因子(除去它本身 ) 之和等于该完全数. 例如, 6是一个完全 数. 因为1+2+。