4.数论的其它问题.ppt

1、素性检测,1、素数的个数,定理：素数有无穷个 证：若只有有限个，设 为所有的素数。考察 因Npi,所以N为合数。如果N为合数，根据算术基本定理，则N必以某些 为因子。这是不可能的！,2、素数的分布,虽然素数有无穷多个，但随着整数范围越来越大，素数似乎越来越稀少。 1，100-25 1000,1100-16 100000, 100100-6 10000000,10000100-2,关于素数个数的近似公式首先是Gauss 于 1792年给出的,但他当时没能给出证明. 勒让德也曾给出,后来，Gauss还给出了近似公式：,1852年，俄国数学家切比雪夫证明了 这里a=0.92, b=1.055. 18

2、92年，英国数 学家希尔维斯特改进切比雪夫的结果，得 到a=0.956, b=1.044.,3、小素数,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 于 1914年编织出了10000000以内的素数表。,试除法 假设我们已经找到了前n个素数p1=2, p2=3, .,pn, 为了寻找下一个素数我们从pn+2开始依次检验每一个整数N, 看N是否能被某个pi, i=1,2,.,n整除. 如果N

3、能被前面的某个素数整除, 则N为合数. 否则N即为下 一个素数pn+1. 为提高算法的效率，只需用不超过 的素数去除N。,4、素数的判别,威尔逊判别法 n是素数的充要条件是 不过该算法的运算量为O(nlogn2),计算量太大。,Fermat判别法 如果p是素数，a与p互素，那么 实际上，大约2500年前，中国古代数学家 就发现了上述结论。他们由此得出：如 果 ,则n为素数。该判别法 的运算量为O(log3n).,但这是一个必要条件，非充分条件。反过来结论并不成立。例如: 但是341=11x34为合数！ 称使得 成立的p为伪素数。,注意同余的计算：,也是无穷多个。实际上，数学家迈罗在1903年证

4、明，如果n为伪素数，那么2n-1也是伪素数。 不过，同素数个数相比，伪素数的个数非常少。例如，在21010之内，伪素数不到素数的百万分之三。 因此，可以认为 Fermat定理的逆定理几乎成立，这也可以成为概率测试的依据。,伪素数有多少个？,利用伪素数表，可以给出判别素数的新方法：如果p不整除2n-1, 则p为合数；如果p整除2n-1, 且在伪素数表中，则p为合数，否则，p是素数。 伪素数可以推广到a-伪素数（相对2-伪素数）。令人惊奇的是，存在这样的数p, 它对任何a都是伪素数。例如，p=561=31117就是这样一个伪素数，即 还有1105,1729等也是这样，它们都是合数.,这样的数称为绝

5、对伪素数，也称迈克尔数。如果迈克尔数只有有限个，则对nM, 素数的判别变得比较容易。但迈克尔可能有无限个，这使得直接用Fermat 定理判别素性变得困难。,n-1检验法 假设n-1=F*R, FR, gcd(F, R)=1. 如果对F的每一个素因子q都存在一个整数a1满足: 则n是素数。,年数学家Adleman, Rumely, Cohen和Lenstra研究出一种非常复杂、具有高度技巧的素数判别方法，检验一个位数的素性只需秒，对一个位数，只要秒，而一个位数只用秒。如果用试除法，判别一个位数的素性要一百亿年！,5、概率素数,Lehmann:对于给定的数p，随机选取a1或-1, 那么p为合数；

6、（）如果 J=1或-1,那么p不是素数的可能性最多是1/2.,其中a就是p可能是素数的一个证据,多找几个证据，比如k个，那么p不是素数的可能性不超过1/2k. 利用上述算法可以产生大的随机素数： （1）产生随机数p; （2）确保p不被较小的素数整除。 （3）产生随机数a, 利用上述算法检测p的素性。直到经过多次测试为止。,Miller-Rabin:,原理： 若n是素数，则 an-1 1 mod n 两边逐次开方，得到 a(n-1)/2, a(n-1)/4, , a(n-1)/2k = am = b 且第一个不为1的值必是-1 其中记n-1=2km, 记bam mod n an-1/ 2k mo

7、d n 对于n和一个随机数a： 如果b1 mod n，则n很可能是素数 否则必不是素数,算法： 待测数n 计算k, m，其中n-12km 选择a 计算bam mod n 如果b1则a是证据(witness) 否则重复bb*b mod n做k回 期间如果遇有b-1，则是witness 否则n是合数 a的可信概率是3/4,Miller-Rabin算法：用来测试一个整数是否是素数 WITNESS(a,n) 设bkbk-1b0是(n-1)的二进制表示 d1 for ik downto 0 do xd d(dd) mod n if (d=1 & x1 & xn-1) return TRUE if (bi

8、=1) then d(da) mod n if (d1) return TRUE else return FALSE 如果n不是素数，则返回FALSE的概率(即失败概率)小于1/4，k次后失败概率为1/4k.（n 可能是素数，为3/4） 如返回TRUE，说明n不是素数。,素数生成过程: 随机选择一个奇数n(如通过伪随机数发生器) 随机选择a, 使an 进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到 如果通过了足够次数的测试,认为n是素数,否则转到.,6、素性判别的多项式算法 给定一个n位的整数，假设某一算法能在f(n)步内判断出该整数是否素数。如果f(n)是

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

10、一定为素数。例如，M_11=2047=23x89是合数。,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都是素数。,原根与离散对数,Euler定理表明,对两个互素的整数a,n, a(n) 1 mod n 问： (n) 是不是使上式成立的最小整数？ 定义：n1是整数，a与n互素, 使得 am 1 mod n 成立的最小整数m称a对模n的指数。 对某个a,若m=(n),则称a是模n的一个原根 如：n=7, (7)=6,而 36 1 mod 7,3是原根。,定理：对于素数p,若a是p的一个原根,则: a,a2, ,ap-1关于p两两不同余,从而构成了p的非0剩余系.,若a是素数p的一个原根,则对任意整数b,b0 mod p,存在唯一的整数i, 1i(p-1),使得:bai mod pi称为b以a为基模p的离散对数,记作inda,p(b).容易知道: inda,p(xy)= inda,p(x)+inda,p(y) mod (p) inda,p(xr)= rin