第八章_原根与离散对数

电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数第八章原根与离散对数电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数第八章原根与离散对数8.1指数和原根（掌握）8.2原根的存在性（理解）8.3离散对数（熟练）电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数8.1指数和原根定义8.1.1设m是大于1的正整数，如果(a，m)=1，则使同余式ad1(modm)成立的最小正整数d称为a对模m的指数（或阶），记为ordm(a)．如果a对模m的指数是(m)，则a称为模m的一个原根．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数和原根例8.1.1n=10，取模10的简化剩余系1，3，7，9，因为11≡1（mod10）；32≡9（mod10），33≡7（mod10），34≡1（mod10）；72≡9（mod10），73≡3（mod10），74≡1（mod10）；92≡1（mod10）；电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数和原根所以ord10（1）=1，ord10（3）=4，ord10（7）=4，ord10（9）=2，他们都是的因子，且3和7均是模10的原根。例8.1.2n=8取模8的一个简化剩余系1，3，5，7，因为11≡1（mod8）；32≡1（mod8）；52≡1（mod8）；72≡1（mod8）；所以ord8（1）=1，ord8（3）=2，ord8（5）=2，ord8（7）=2，而，故模8没有原根。(10)4(8)4返回电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数和原根我们再次指出：与m互素的(m)个剩余类构成一个乘法群Sm．于是显然一个数a对模m的指数ordm(a)就是它所在剩余类在群中的阶，如果模m存在原根，则Sm构成一个乘法循环群，而原根就是Sm中的生成元．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质假设m是大于1的正整数，(a，m)=1，a对模m的阶为ordm(a)．性质1．如果ab(modm)，则ordm(a)=ordm(b)．性质2．ad1(modm)的充分必要条件是：ordm(a)d．性质3．ordm(a)(m)．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质4．设a1是a模m的逆元，即a1a1(modm)，则ordm(a1)=ordm(a)．性质5．下列ordm(a)个数：1=a0，a，…，模m两两不同余．特别地，当a是模m原根时，即ordm(a)=(m)时，这(m)个数构成模m简化剩余系．性质6．adak(modm)，则dk(modordm(a))．()1mordaa电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质7设k为非负整数，则而且在模m的简化剩余系中，至少有(ordm(a))个数对模m的指数等于ordm(a)．特别地，如果a是一个模m的原根，则ak也是模m的原根的充分必要条件是((m)，k)=1．性质8如果模m存在一个原根，则模m共有((m))个不同的原根．()()(())，kmmmordaordaordak返回电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质9ordm(ab)=ordm(a)ordm(b)的充分必要条件是(ordm(a)，ordm(b))=1．性质101）如果nm，则ordn(a)ordm(a))．2）如果(m2，m1)=1，则性质11如果(m2，m1)=1，则对任意整数a1，a2，必存在a使得1212()[()()]mmmmordaordaorda，121212()[()()]mmmmordaordaorda，电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质9证明充分条件证明：首先我们有mmmmmmord(a)ord(b)ord(a)ord(b)ord(b)ord(a)(ab)=(a)(b)=1(modm).性质9．ordm(ab)=ordm(a)ordm(b)的充分必要条件是(ordm(a)，ordm(b))=1．得ordm(ab)|ordm(a)ordm(b)电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数故电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质必要条件证明：我们有于是由ordm(ab)=ordm(a)ordm(b)得ordm(a)ordm(b)[ordm(a)，ordm(b)]，故(ordm(a)，ordm(b))=1．[()()][()()][()()]()1(mod)mmmmmmordaordbordaordbordaordbababm，，，性质9．ordm(ab)=ordm(a)ordm(b)的充分必要条件是(ordm(a)，ordm(b))=1．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质10证明1）我们有由于nm，则于是故ordn(a)ordm(a)．()1nordana()1mordama()1,mordana()1(mod)mordaan性质10．(1)如果nm，则ordn(a)ordm(a))电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质2）我们有12[()()]11(mod)mmordaordaam，12[()()]21(mod)mmordaordaam，mmordaordaamm1212[()()]121(mod)，因(m,m)=1有性质10．(2)(m2，m1)=1，则1212()[()()]mmmmordaordaorda，电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质如果存在i使得则于是因此故121(mod)iamm11(mod)iam21(mod)iam1()mordai2()mordai12[()()]mmordaordai，1212()[()()]mmmmordaordaorda，性质10．(2)(m2，m1)=1，则1212()[()()]mmmmordaordaorda，电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数指数的性质性质11证明考虑同余式组xa1(modm1)，xa2(modm2)，由于(m2，m1)=1，则由中国剩余定理有xa(modm1m2)．由性质1有：再由性质10得证．111()(),mmordaorda222()()mmordaorda性质11如果(m2，m1)=1，则对任意整数a1，a2，必存在a使得121212()[()()]mmmmordaordaorda，电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数8.2原根的存在性从前面例8.1.2知道，并不是所有的模m都有原根的。我们已经知道，当p是素数时，模p剩余类构成有限域GF(p)，域中存在本原元，显然这个本原元是GF(p)中非零元构成的循环群的生成元，也就是模p的原根．于是我们有下面的定理并给予直接证明．定理只涉及奇素数．容易验证，唯一的偶素数2的情形下1是原根．例8.1.2电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性定理8.2.1如果p是奇素数，则存在模p的原根．证明模p的简化剩余系是{1，2，…，p1}，设它们的所有不同指数为：d1，d2，…，dr．令D是它们的最小公倍数，D=[d1，d2，…，dr]．设D的标准分解式为1212Dkkqqq电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性于是对于一个存在一个di使设则有对于k个，存在k个xa（设它们为y1，y2，…,yk），它们的指数遍历这k个，由于这k个两两互素，由上节的性质9，我们有Y=y1y2…yk的指数等于D．jjqjijdaqjpijordx=d=aq（）()jjjjjjapjjaqaqordxqaaqa（）=，jjqjjqjjq电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性面我们考察D与(p)=p1的关系．一方面我们有Dp1．另一方面，简化剩余系中的每个数都是同余式xD1(modp)的解，则该同余式有p1个解，因此Dp1．于是我们最后有D=p1．这说明Y就是模p的原根．定理证毕．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性定理8.2.2模m的原根存在的充分必要条件是m=2，4，p，2p，其中p是奇素数，1．定理1是=1时p的特例．当m=2时，1是原根．当m=4时，3是原根．定理2的证明超出了本书的范围．定理2说明，只有当m=2，4，p，2p时，与模m的简化剩余系才构成一个循环群并具有生成元电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性定理8.2.3设(m)的不同素因子为q1，q2，…，qk，则g（(g，m)=1）是模m的一个原根的充分必要条件是，i=1，2，…，k．证明必要条件是显然的，因为(m)是使gn1(modm)的最小正整数．充分条件证明．用反证法．假设g不是模m的原根，即它的指数ordm(g)(m)，那么ordm(g)(m)，()1(mod)imqgm电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性于是必有一个qi使则所以得到矛盾结果．故g是模m的原根．()()immqordg(),()immqsordg()()mimordgsq()()1(mod)immqordgsggm电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性例8.2.2设m=41，则(41)=40=235，q1=2，q2=5，于是所以g是模41原根的充分必要条件是：g81(mod41)，g201(mod41)，(g，41)=1．我们对模41的简化剩余系进行逐一验证．181(mod41)，2810(mod41)，2201(mod41)，381(mod41)，4818(mod41)，4201(mod41)，201(m)=q2()8mq电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性5818(mod41)，5201(mod41)，6810(mod41)1(mod41)，62040(mod41)1(mod41)．故6是模41的一个原根．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数原根的存在性电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数8.3离散对数如果模m有一个原根g，则g0=1，g1，g2，…，g(m)1组成模m的一个简化剩余系．这也就是说对于任一整数a，(a，m)=1，都可以唯一地表示为ag(modm)，0(m)-1．电子科技大学计算机科学与工程学院UESTCPress第八章原根与离散对数离散对数我们现在引入离散对数的概念．定义8.3.1设g是模m的一个原根．对于任一整数a，(a，m)=1，都有ag(modm)，0(m)-1，我们把称为以g为底的a对模m的离散对数，记为indga．离散对数也称为指标．之所以称为离散对数，是因为它定义在离散的整数集合上，而不是象普通对数那样定义在连续的实数集合上．电子科技大学计算机科学与工程学院UESTCPr