第八章_原根与离散对数试卷.ppt

原根的存在性 于是对于一个 存在一个di使 设 则有 对于k个 ，存在k个xa（设它们为y1，y2，…,yk），它们的指数遍历这k个 ，由于这k个 两两互素，由上节的性质9，我们有 Y = y1y2…yk 的指数等于D． 原根的存在性 面我们考察D与?(p) = p?1的关系．一方面我们有 D? p?1． 另一方面，简化剩余系中的每个数都是同余式 xD ? 1 (mod p) 的解，则该同余式有p?1个解，因此 D ? p?1． 于是我们最后有 D = p?1． 这说明Y就是模p的原根．定理证毕． 原根的存在性 定理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的简化剩余系才构成一个循环群并具有生成元 原根的存在性 定理8.2.3　设?(m)的不同素因子为 q1，q2，…，qk， 则g（(g，m) = 1）是模m的一个原根的充分必要条件是 ，i = 1，2，…，k． 证明　必要条件是显然的，因为?(m)是使 gn ? 1 (mod m) 的最小正整数． 充分条件证明．用反证法． 假设g不是模m的原根，即它的指数ordm(g)??(m)，那么 ordm(g)??(m)， 原根的存在性 于是必有一个qi使 则 所以 得到矛盾结果．故g是模m的原根． 原根的存在性 例8.2.2　设m = 41，则?(41) = 40 = 23?5，q1 = 2，q2 = 5，于是 所以g是模41原根的充分必要条件是： g8 ? 1 (mod 41)，g20 ? 1 (mod 41)，(g，41) = 1． 我们对模41的简化剩余系进行逐一验证． 18 ? 1 (mod 41)， 28 ? 10 (mod 41)，220 ? 1 (mod 41)， 38 ? 1 (mod 41)， 48 ? 18 (mod 41)，420 ? 1 (mod 41)， 原根的存在性 58 ? 18 (mod 41)，520 ? 1 (mod 41)， 68 ? 10 (mod 41) ? 1 (mod 41)，620 ? 40 (mod 41) ? 1 (mod 41)． 故6是模41的一个原根． 原根的存在性 8.3　离散对数 如果模m有一个原根g，则 g0=1，g1，g2，…，g?(m) ?1 组成模m的一个简化剩余系．这也就是说对于任一整数a，(a，m) = 1，都可以唯一地表示为 a ? g? (mod m)，0? ? ? ?(m)-1． 离散对数 例8.3.1　18 = 2?32，属于2p?的形式，所以模18存在原根，可以求出模18的一个原根是5，则模18简化剩余系与模?(18) = 6的完全剩余系的一一对应关系： 模?(18) 完全剩余系 0 1 2 3 4 5 模18简化剩余系 1 5 7 17 13 11 离散对数 我们现在引入离散对数的概念． 定义8.3.1　设g是模m的一个原根．对于任一整数a，(a，m) = 1，都有a ? g? (mod m)，0? ? ? ?(m)-1，我们把?称为以g为底的a对模m的离散对数，记为indg a．离散对数也称为指标． 之所以称为离散对数，是因为它定义在离散的整数集合上，而不是象普通对数那样定义在连续的实数集合上． 离散对数 例8.3.2　可以求出模18的一个原根是5，以5为底模18的离散对数： 显然如果a ? b(mod m)，则 indg a = indg b (mod ?(m)) ， 反之，如果indg a = indg b (mod ?(m)) ，则 a ? b(mod m)， a 1 5 7 11 13 17 ? 0 1 2 5 4 3 离散对数 离散对数具有下列与普通对数相似的性质． 性质1　indg 1 = 0，indg g = 1． 性质2　indg (ab) ? indg a + indg b (mod ?(m))． 性质3　indg an ? n?indg a (mod ?(m))，其中n?1． 性质4　如果g1也是模m的一个原根，则 证明　性质1显然． 性质2证明：因为 所以 indg (ab) ? indg a + indg b (mod ?(m))． 性质3是性质2的直接推论． 性质2　indg (ab) ? indg a + indg b (mod ?(m))． 性质4证明： 设