第6章素性检验.pdfVIP

第五章素性检验 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 引理设d,n都是正整数,如果d能整除n,则2 -1能 整除2n-1 证明:因为d|n,所以存在整数n=dq,因此, 2n d q d d q-1 d q-2+…+1 -1=(2 ) -1=(2 -1)((2 ) + (2 ) ),故成立 定理1 存在无穷多个基于2的拟素数 5.1拟素数 证明: (i)证明如果n是对于基2的拟素数,则m=2n-1,也是 对于基2的拟素数.以为n是拟素数,所以n是奇合数 并且2n-1≡1(modn),且有因素分解式 d n n=dq,1d,qn,由引理, 2 -1| 2 -1, 从而m是合 数,现证明2m-1≡1(modm), 将m-1=2(2n-1-1),又 即m-1=kn, 由引理 2n-1| 2m-1-1,即m| 2m-1-1,同余式2m-1≡1(modm),成 立,它也是基于2的拟合数,证毕 5.1拟素数 定理2 设n是一个奇合数,则 (i) n是对于基b的拟合数,当且仅当b模n的指数整除 n-1 (ii) 如果n分别是对于基b 和b 的拟合数,则n是对于 1 2 基b b 的拟合数 1 2 (iii)如果n是对于基b的拟合数,则则n是对于基b-1 的 拟合数 (ⅳ)如果一个整数b,(b,n)=1,使得同余式 bn-1≡1(modn)不成立,则模n的简化剩余系中至少有 一半的数同样使同余式不成立 5.1拟素数 定义2 设m1是整数,a是与m互素的正整数,则使 得ae ≡1(modm)成立的最小正整数e叫做对模m 的指数, 记做ordm(a),当a对m的指数是欧拉函数 时则a叫做模m的原根 定理设m1是整数,a是与m互素的正整数,则整数 d使得ad ≡1(modm)的充要条件是ordm(a)|d 5.1拟素数 (i)如果bn-1≡1(modn), 由指数的定义知道我们有 Ordn(b)|n-1 反过来,如果Ordn(b)|n-1,则有引理有 b Ordn(b)-1|b n-1-1,从而bn-1≡1(modn) (ii) 由模运算的性质和拟合数的定义易证 5.1拟素数 (iii) 因为n是对于模n的拟合数,因此,bn-1≡1(modn) -1)n-1 n-1 -1 (b ≡(b ) ≡1(modn) (ⅳ)设b ,.., b , b ,…, b ,是模m的简化剩余系,其中前 1 s s+1 ϕ(n ) S个数使得同余式bn-1≡1(modn)成立,根据假设,存在一个 整数b,(b,n)=1,使得同余式不成立,有(ii)和(iii),有s个模n的 不同简化剩余bb , bb ,…, bb , 从而 1 2 s s ≤ϕ(n) −s 从而