资源描述：
《第6章素性检验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章素性检验5.1拟素数5.2Euler素数5.3强拟素数5.1拟素数由费马定理,如果n是素数,则对任意整数b,(b,n)=1,有bn-1≡1(modn),反过来,若一个整数b,(b,n)=1,使得bn-1!≡1(modn),定义1设n是一个奇合数,如果整数b,(b,n)=1使得同余式bn-1=1(modn),成立,则n叫做对于基b的拟素数5.1拟素数引理设d,n都是正整数,如果d能整除n,则2d-1能整除2n-1证明:因为d
2、n,所以存在整数n=dq,因此,2n-1=(2d)q-1=(2d-1)((2d)q-1+(2d)q-2+…+1),故成
3、立定理1存在无穷多个基于2的拟素数5.1拟素数证明:(i)证明如果n是对于基2的拟素数,则m=2n-1,也是对于基2的拟素数.以为n是拟素数,所以n是奇合数并且2n-1≡1(modn),且有因素分解式n=dq,14、2n-1,从而m是合数,现证明2m-1≡1(modm),将m-1=2(2n-1-1),又即m-1=kn,由引理2n-1
5、2m-1-1,即m
6、2m-1-1,同余式2m-1≡1(modm),成立,它也是基于2的拟合数,证毕5.1拟素数定理2设n是一个奇合数,则(i)n是对于基b的拟合数,当且仅当b模n的指数整除
7、n-1(ii)如果n分别是对于基b和b的拟合数,则n是对于12基bb的拟合数12(iii)如果n是对于基b的拟合数,则则n是对于基b-1的拟合数(ⅳ)如果一个整数b,(b,n)=1,使得同余式bn-1≡1(modn)不成立,则模n的简化剩余系中至少有一半的数同样使同余式不成立5.1拟素数定义2设m>1是整数,a是与m互素的正整数,则使得ae≡1(modm)成立的最小正整数e叫做对模m的指数,记做ord(a),当a对m的指数是欧拉函数m时则a叫做模m的原根定理设m>1是整数,a是与m互素的正整数,则整数d使得ad≡1(modm)的充要条件是ord(
8、a)
9、dm5.1拟素数(i)如果bn-1≡1(modn),由指数的定义知道我们有Ord(b)
10、n-1n反过来,如果Ord(b)
11、n-1,则有引理有nbOrdn(b)-1
12、bn-1-1,从而bn-1≡1(modn)(ii)由模运算的性质和拟合数的定义易证5.1拟素数(iii)因为n是对于模n的拟合数,因此,bn-1≡1(modn)(b-1)n-1≡(bn-1)-1≡1(modn)(ⅳ)设b,..,b,b,…,,b是模m的简化剩余系,其中前1ss+1ϕ()nS个数使得同余式bn-1≡1(modn)成立,根据假设,存在一个整数b,(b,n)=1,使得同
13、余式不成立,有(ii)和(iii),有s个模n的不同简化剩余bb,bb,…,bb,从而12ssns≤ϕ()−从而成立5.1拟素数ⅳ告诉我们,对于大奇数b,(b,n)=1,使得同余式bn-1≡1(modn)不成立,那么,对于随机选取的整数b,,(b,n)=1,我们有50％的概率判断出n是合数5.1拟素数¢Fermat素性检验¢(i)随机选择整数b,01,则n不11是素数,如果d=1,则计算n−1,如果不bn(mod)11成立,则n不是素数,如果成立,则n是合数的可能性就小于1/2
14、¢(ii)重复上述过程,直至第t步,,则n是合数的可能性就小于1/2t,或者说n是素数的可能性是1-1/2t5.1拟素数¢上述过程简单归纳为:给定奇整数n≥3,和安全参数t1.随机选择整数b,2≤b≤n-2,(b,n)=12.计算r=bn-1(modn)3.如果r≠1,则n是合数4.上述过程重复t次5.1拟素数定义2合数n称为Carmichael(卡米克尔数),如果所有的正整数b,(b,n)=1,都有同余式bn-1≡1(modn)成立例1整数561=3*11*17是一个Carmichael数证明:如果,(b,561)=1,则(b,3)=(b,11
15、)=(b,17)=1由费马小定理,对任意整数有b2≡1(mod3)b10≡1(mod11)b16≡1(mod17)5.1拟素数¢从而b560≡(b2)280≡1(mod3)b560≡(b10)56≡1(mod11)b560≡(b16)35≡1(mod17)由孙子定理对于所有的bb560≡1(mod561)成立5.1拟素数¢定理3设n是一个奇合数,¢(i)如果n是一个大于1的平方数,则n不是Carmichael数¢(ii)如果n=p…p是一个无平方数,则n是1kCarmichael数的充要条件P-1
16、n-11≤i≤ki定理4每个Carmichael
17、数至少是三个不同素数的乘积¢注1.存在无数Carmichael数,2.当n充分大时,区间¢[2,n]内的Carmichael数的个数大于
