数学实验之五---素数

《数学实验之五---素数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、82930313233经过众多学者的艰辛努力,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(nlogn^2),计算量太大。Fermat判别法如果p是素数，

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

4、-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年，缪内发现了素性判别与黎曼猜想之间的一个深刻联系

5、。他的结论是：在广义黎曼假设下，存在常数C,对任何整数n,若n为合数，则存在a

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

7、多项式的话，则称该算法具有多项式复杂性，称该问题是“多项式可解的”。如果不存在一个算法其具有多项式的计算复杂性，则称该问题属于NP问题。2002年8月，印度理工大学计算机系的三位学者提出了整数素性判别的多项式算法！即素性判别问题是P类问题。他们指出算法复杂性一般为O(n^12)。如果提供某些启发线索的话，算法的复杂性可以降到O(n^6)甚至O(n^3).一个令人关注的问题是，该算法是否会威胁现有的RSA公钥密码体系的安全？4、最大的素数Mersenne数形如的数称为Mersenne数。利用Mersenne数可以构造