数论算法》教案_5章(原根与离散对数).doc

《数论算法》 第五章 原根与离散对 数1/60第第 5 章章 原原根根与与离离散散对对数数内容内容1. 整数的阶整数的阶 2. 原根原根 3. 有原根的整数有原根的整数 4. 离散对数（指标）离散对数（指标）要点要点1. 原根及其意义原根及其意义 2. 有原根的整数的条件有原根的整数的条件 3. 离散对数及其性质离散对数及其性质5.1 阶阶及及其其基基本本性性质质准准备备知知识识： ：（（1））欧拉定理：欧拉定理：m＞＞1，，(a, m)＝＝1，则，则≡≡1（（mod m））   ma （（2））问题：问题：①①是否是使得上式成立的最小正整数？是否是使得上式成立的最小正整数？   m ②②该最小正整数有何性质？该最小正整数有何性质？(一) 阶阶和和原原根根概概念念【【定义定义 5.1.1】】设设 m＞＞1，，(a, m)＝＝1，则使得，则使得≡≡1（（mod m））ea成立的最小正整数成立的最小正整数 e 叫做叫做 a 对模对模 m 的的阶阶（或（或指数指数）） ，记作，记作 (a)。

若若 a 的阶的阶 e＝＝，则，则 a 叫做模叫做模 m 的的原根原根mord   m (一) 应应用用： ：Diffie—Hellman 密密钥钥交交换换算算法法公钥算法的核心：公钥算法的核心：（（1））仅依赖公开信息不足以对算法构成威胁；仅依赖公开信息不足以对算法构成威胁；《数论算法》 第五章 原根与离散对 数2/60（（2））掌握私钥者可轻易获得信内容掌握私钥者可轻易获得信内容 全局公开量全局公开量 q 素数素数q 的原根（的原根（＜＜q））  生成用户密钥生成用户密钥用户用户 A选择秘密的选择秘密的 ＜＜qAXAX计算公开的计算公开的 ≡≡（（mod q））AYAYAX 用户用户 B选择秘密的选择秘密的 ＜＜qBXBX计算公开的计算公开的 ≡≡（（mod q））BYBYBX ………………交换公开密钥交换公开密钥 A→→B：： AYB→→A：： BY生成公共密钥生成公共密钥 K用户用户 A计算计算 K≡≡（（mod q））   AX BY用户用户 B计算计算 K≡≡（（mod q））   BX AY说明：说明：K≡≡≡≡≡≡（（mod q））   AX BY   BX AYBAXX 例：例： 素数素数 q＝＝353，原根，原根αα＝＝3  A 选选＝＝97，， 计算计算≡≡≡≡40 mod 353AXAY973  B选选＝＝233，， 计算计算≡≡≡≡248 mod 353BXBY2333  A 与与 B 交换交换  A 计算密钥计算密钥 K≡≡≡≡160 mod 35397248  B 计算密钥计算密钥 K≡≡≡≡160 mod 35323340《数论算法》 第五章 原根与离散对 数3/60(一) 用用定定义义求求阶阶和和原原根根【【例例 1】】 （（按定按定义义求求阶阶和原根和原根））m＝＝7，则，则(7)＝＝6。

且且 ≡≡1，，≡≡1，，≡≡1，，≡≡1，，≡≡1，，≡≡1（（mod 7））113263346526故对模数故对模数 7 而言，而言，1，，2，，3，，4，，5，，6 的阶分别为的阶分别为 1，，3，，6，，3，，6，，2列表表示为列表表示为a123456(a)mord136362因此，因此，3，，5 是模是模 7 的原根例例 2】】 （（快速求快速求阶阶））m＝＝14＝＝2·7，， (14)＝＝6，则，则 ≡≡1，，≡≡－－1，，≡≡－－1，，≡≡1，，11333539≡≡1，，≡≡1（（mod 7））311213 列表列表a13591113(a)mord166332故故 3，，5 是模是模 14 的原根例例 3】】 （（无原根的整数无原根的整数））m＝＝15＝＝3··5，， (15)＝＝8，则，则 a12478111314(a)mord14244242故模数故模数 15 没有原根没有原根同理，可知模数同理，可知模数 m＝＝9 时，其原根为时，其原根为 2，，5；而整数；而整数 8 则没有则没有《数论算法》 第五章 原根与离散对 数4/60原根。

原根也可以计算验证也可以计算验证 5 是模是模 3、、6、、9、、18 的原根一) 阶阶的的性性质质【【定理定理 5.1.1】】设设 m＞＞1，，(a, m)＝＝1，，d 为正整数，则为正整数，则≡≡1（（mod m）） (a) ││ddamord即即 d≡≡0（（mod (a)））mord（（证证）充分性：设）充分性：设(a) ││d，则，则 d＝＝k··(a)，从，从mordmord 而而≡≡≡≡≡≡1（（mod m））da   aordkma      kaordma必要性：反证：若必要性：反证：若≡≡1 且且(a) d，则由欧几里得，则由欧几里得damord 除法，有除法，有d≡≡(a)·q＋＋r，， 0＜＜r＜＜(a)mordmord从而从而≡≡≡≡≡≡1（（mod m））rara     qaordmada与与(a)的最小性矛盾的最小性矛盾mord【【推论推论 1】】(a) ││(m)mord 意义意义：：(a)必是必是(m)的因子，故求的因子，故求(a)只需计只需计mord mord算算，其中，其中 i││(m)ia 【【例例 4】】 （（用定理用定理 5.1.1 结论结论快速求快速求阶阶及原根及原根）） （（例例 7）求）求 (5)的值。

的值17ord《数论算法》 第五章 原根与离散对 数5/60（（解解））(17)＝＝16，只需计算，只需计算（（mod 17）） ，其中，其中 d5 d＝＝1，，2，，4，，8，，16（（实际实际上上不必不必计计算算）） 165≡≡5，，≡≡8，，≡≡13≡≡－－4，，≡≡16≡≡－－1（（mod 15254585 17））所以，所以，(5)＝＝16，即，即 5 是模是模 17 的原根17ord【【例例 5】】求求(4)、、(5)、、(7)的值33ord33ord33ord（（解解））(33)＝＝20 只需计算只需计算、、、、（（mod 33）） （（i＝＝1, 2, 4, 5, 10）） i4i5i7≡≡1（（mod 33）） ；；54≡≡23（（mod 33）） ，，≡≡1（（mod 33）） ；；55105≡≡10（（mod 33）） ，，≡≡1（（mod 33））57107∴ (4)＝＝5，，(5)＝＝10，，(7)＝＝1033ord33ord33ord【【推论推论 2】】设设 p 是奇素数，是奇素数，也是奇素数，也是奇素数，p a，则，则21 p（（1）若）若 a 是模是模 p 的二次剩余，则的二次剩余，则 a 不是不是 p 的原根，且当的原根，且当 a≡≡1（（mod p）时，）时，(a)＝＝1；当；当 a1（（mod p）时，）时，pord(a)＝＝；；pord21 p（（2）若）若 a 是模是模 p 二次非剩余，则当二次非剩余，则当 a≡≡p－－1（（mod p）时，）时， (a)＝＝2；当；当 ap－－1（（mod p）时，）时，(a)＝＝p－－1。

pordpord（（3）此时，）此时，p 有有－－1＝＝个原根21 p 23 p（（4）当）当＝＝2 为偶素数时，必有为偶素数时，必有 p＝＝5，其平方剩余为，其平方剩余为21 p《数论算法》 第五章 原根与离散对 数6/601 和－和－1≡≡4，平方非剩余为，平方非剩余为 2 和和 3，且，且 2 和和 3 是原根证证）由推论）由推论 1，，(a)││(p)＝＝p－－1＝＝2··，，pord 21 p故故(a)可能为可能为 1, 2, , p－－1pord21 p（（1））a 是模是模 p 二次剩余，则由二次剩余的充分必要条二次剩余，则由二次剩余的充分必要条 件知件知≡≡1（（mod p））21p  a由定理由定理 5.1.1 知知(a)││，但，但是素数，故是素数，故pord21 p 21 p(a)＝＝1 或或 pord21 p而而(a)＝＝1 a≡≡1（（mod p）） ，故结论成立故结论成立pord（（2））a 是模是模 p 的二次非剩余，则由二次剩余的充分必的二次非剩余，则由二次剩余的充分必要条件知要条件知 ≡≡－－1（（mod p））21p a 即即(a) ≠≠，，那么那么，，只有只有pord21 p(a)＝＝2 或或 p－－1 pord（（(a) 也不能为也不能为 1，因为只有，因为只有(1)＝＝1，但，但 1 是平方是平方pordpord剩余，不是非剩余剩余，不是非剩余））而而(a)＝＝2 a≡≡p－－1≡≡－－1（（mod p）） ，，故结论成立。

故结论成立pord（（3））由第由第 4 章结论知章结论知，，p 有有个平方非剩余个平方非剩余，，其中其中21 p只有只有(p－－1)＝＝2，，其余的其余的(a)＝＝p－－1，即原根有，即原根有pordpord－－1＝＝个21 p 23 p（（4）显然《数论算法》 第五章 原根与离散对 数7/60【【例例 6】】取取 p＝＝11，验证推论，验证推论 2解解）首先，直接计算知：）首先，直接计算知：1，，3，，4，，5，，9 是是 11 的二次的二次 剩余，剩余，2，，6，，7，，8，，10 是模是模 11 的二次非剩余且有的二次非剩余且有(1)＝＝1，，11ord(3)＝＝(4)＝＝(5)＝＝(9)＝＝5，，11ord11ord11ord11ord(2)＝＝(6)＝＝(7)＝＝(8)＝＝10，，11ord11ord11ord11ord(10)＝＝211ord【【性质性质 1】】设设(a, m)＝＝1 （（1）若）若 b≡≡a（（mod m）） ，则，则(b)＝＝(a)mordmord（（2））＝＝(a)。

   1ord ammord（（证证）） （（1）已知）已知 b≡≡a（（mod m）） ，所以，所以≡≡≡≡1（（mod m））   aordmb   aordma所以所以(b)││(a)mordmord其次，其次， ≡≡≡≡1（（mod m））   bordma   bordmb所以所以(a)││(b)mordmord∴∴ (b)＝＝(a)mordmord（（2）证法一：由）证法一：由≡≡≡≡1（（mod m））      aord1ma      1aord ma知知()││(a);mord1 amord由由 a≡≡1（（mod m）知）知≡≡1（（mod m）。