《数论算法》 第五章 原根与离散对数
第 5 章 原根与离散对数
1. 整数的阶 内容 2. 原根 3. 有原根的整数 4. 离散对数（指标） 1. 原根及其意义 要点 2. 有原根的整数的条件 3. 离散对数及其性质 5.1 阶及其基本性质
准备知识：
（1） 欧拉定理：m＞1，(a, m)＝1，则
a??m?≡1（mod m）
（2） 问题：
①??m?是否是使得上式成立的最小正整数？ ②该最小正整数有何性质？ (一) 阶和原根概念
【定义5.1.1】设m＞1，(a, m)＝1，则使得
ae≡1（mod m）
成立的最小正整数e叫做a对模m的阶（或指数），记作
ordm(a)。若a的阶e＝??m?，则a叫做模m的原根。(二) 应用：Diffie—Hellman密钥交换算法 公钥算法的核心：
（1） 仅依赖公开信息不足以对算法构成威胁； （2） 掌握私钥者可轻易获得信内容。
1/58
《数论算法》 第五章 原根与离散对数
全局公开量
q 素数
? q的原根（?＜q） 用户A 用户B …
交换公开密钥
A→B： YA B→A： YB
生成公共密钥K 用户A 计算 K≡?YB?用户B 计算 K≡?YA?说明：K≡?YB?例：
? 素数q＝353，原根α＝3
? A选XA＝97， 计算YA≡397≡40 mod 353 ? B选XB＝233， 计算YB≡3233≡248 mod 353 ? A与B交换
? A计算密钥 K≡24897≡160 mod 353 ? B计算密钥 K≡40233≡160 mod 353
(三) 用定义求阶和原根
2/58
XAXA生成用户密钥 选择秘密的XA XA＜q 计算公开的YA YA≡?XA（mod q） 选择秘密的XB XB＜q 计算公开的YB YB≡?XB（mod q） …… （mod q） （mod q） XB≡?YA?XB≡?XAXB（mod q）
《数论算法》 第五章 原根与离散对数
【例1】（按定义求阶和原根）m＝7，则?(7)＝6。且
11≡1，23≡1，36≡1，43≡1，56≡1，62≡1（mod 7） 故对模数7而言，1，2，3，4，5，6的阶分别为1，3，6，3，6，2。列表表示为
a 1 2 3 3 6 4 3 5 6 6 2 ordm(a) 1
因此，3，5是模7的原根。 【例2】（快速求阶）m＝14＝2·7， ?(14)＝6，则
11≡1，33≡－1，53≡－1，93≡1，
113≡1，132≡1（mod 7）
列表
a 1 3 6 5 6 9 3 11 13 3 2 ordm(a) 1 故3，5是模14的原根。
【例3】（无原根的整数）m＝15＝3·5， ?(15)＝8，则
a 1 2 4 4 2 7 4 8 4 11 13 14 2 4 2 ordm(a) 1 故模数15没有原根。
同理，可知模数m＝9时，其原根为2，5；而整数8则没有原根。
也可以计算验证5是模3、6、9、18的原根。
3/58
《数论算法》 第五章 原根与离散对数
(四) 阶的性质
【定理5.1.1】设m＞1，(a, m)＝1，d为正整数，则
ad≡1（mod m） ? ordm(a) │d
即d≡0（mod ordm(a)）
（证）充分性：设ordm(a) │d，则d＝k·ordm(a)，从而
a≡adk?ordm?a?≡ad?ordm?a?k?≡1（mod m）
必要性：反证：若a≡1且ordm(a) d，则由欧几里得除法，有
d≡ordm(a)·q＋r， 0＜r＜ordm(a)
从而
a≡aarr?ordm?a?q?≡ad≡1（mod m）
与ordm(a)的最小性矛盾。
【推论1】ordm(a) │?(m)。
意义：ordm(a)必是?(m)的因子，故求ordm(a)只需计算ai，其中i│?(m)。
【例4】（用定理5.1.1结论快速求阶及原根）（例7）求
ord17(5)的值。
（解）?(17)＝16，只需计算5d（mod 17），其中d＝1，2，4，8，16（实际上516不必计算）。
51≡5，52≡8，54≡13≡－4，58≡16≡－1（mod 17）
4/58