《数论算法》 第五章 原根与离散对数
则分别存在非负整数u, r，使得
x0≡gu（mod m），a≡gr（mod m）
由（3）得
gnu≡gr（mod m）
由定理5.3.1知 nu≡r（mod ?(m)）
（可以理解为将方程gnu≡gr（mod m）两边同时以g为底取
对数，但要注意取对数后模数变为?(m)）
即方程 ny≡r（mod ?(m)） （4） 有解（且解为y≡u（mod ?(m)）），故
（n,?(m)）│r＝dlogga
反之，若?n,??m??r?dlogga，则方程（4）有解
y≡u（mod ?(m)）
且解数为d＝(n,?(m))。因此，方程（3）有解
x0≡gu（mod m）
且解数也为d＝(n,?(m))
【推论】在定理5.5.1条件下，a是模m的n次剩余的充
??m?d分必要条件是a≡1（mod m），其中d＝(n，?(m))。 （定理5.5.1：设m＞1，g是模m的一个原根，(a, m)＝1，
n则同余方程x≡a（mod m）有解?（n,?(m)）│dlogga。且在有解的情况下，解数为（n,?(m)））
（证）设a≡gr（mod m），若a是模m的n次剩余，即方程x≡a（mod m）有解，再由定理5.5.1知
n?n,??m??dlogga，即d│r，所以a??m?d≡?gr?41/58
??m?d≡
《数论算法》 第五章 原根与离散对数
?g????m
rd≡1（mod m）
??m?d反之，由a≡1（mod m）知g≡1（mod m）。而g是原根，即g的阶数为?(m)，故由定理5.1.1
??r??m?d??m?r即dr。
??m?d＝
r?(m) d【例】解同余方程x≡23（mod 41）。
（解）d＝(n，?(m))＝(8，?(41))＝(8，40)＝8。 查表得 dlog6(23)＝36 因为836，故原方程无解。
【例】解同余方程x≡37（mod 41）。
（解）d＝(n，?(m))＝(12，?(41) )＝(12，40)＝4。
查表得 dlo6g(37)＝32
因为4│32，，故方程有4个解。 求等价方程，原方程两边同时取对数，得
12dlog6x≡dlog637（mod 40）
即
12dlog6x≡32（mod 40） （5）
（即方程12y≡32（mod 40），对应方程（4）：ny≡r（mod ?(m)），此处n＝12，r＝32） 利用同余性质有
3dlog6x≡8（mod 10）
42/58
8
12《数论算法》 第五章 原根与离散对数
解为
dlog6x≡6（mod 10）
方程（5）的解为
dlog6x≡6，16，26，36（mod 40）
查离散对数的反函数表（即指数函数表）得原方程的解为
x≡66，616，626，636≡39，18，2，23
【定理5.5.2】设m＞1，g是模m的一个原根，(a, m)＝1，则a对m的阶数为
e＝ordm(a)＝
??m? ?indga,??m??特别地，a是模m的原根的充分必要条件为(dlogga, ?(m))＝1。
（证）由定理5.1.4即得。
（定理5.1.4：设整数m＞1，(a, m)＝1，整数d?0，则ordm(a)ordm?a?＝） ?ordm?a?,d?（此处的g即定理中的a，a即定理中的ad，而g是原根（即g的阶数为?(m)），故必存在整数r（1?r??(m)），使得a≡gr（mod m），此处的r即定理中的d，且有r≡dlogga）
【定理5.5.3】设m＞1，g是模m的一个原根，则模m的简化剩余系中，阶是e的整数共有?(e)个。特别地，原根共有?(?(m))个。
（证）因m有原根g，由定理5.1.3，知a＝gd的阶为
d43/58
《数论算法》 第五章 原根与离散对数
ordm(a)＝ordm(gd)＝
??m?ordm?g?＝
?ordm?g?,d????m?,d?显然，a的阶是e的充分必要条件是
(?(m), d)＝
令d＝d????m?,??m?e
??m?d?＝e，即
??m?e（0?d?＜e）。则上式等价于（d?, e）＝1（否d???m?e。而显然有kekk则（d?, e）>1，设（d?, e）＝k，则d＝│?(m)，故(?(m), d)＝??m?ek>??m?e，矛盾）。 而满足（d?, e）＝1的d?显然有?(e)个，故阶为?(m)
的整数个数是?(?(m))，即原根个数为?(?(m))。
5.6 原根与离散对数的应用
5. 6. 1 Diffie—Hellman密钥交换算法
5. 6. 2 原根的应用——ElGamal加密算法 (一) 构造全局变量
? 既可以用于加密，也可以用于签名，其安全性依赖于有限域上计算离散对数的难度 ? 要产生一对密钥，首先选择一素数p，整数模p的一个原根g，随机选取x，g和x都小于p，然后计算：
y≡gx（mod p）
? 公开密钥是y，g，p，其中g，p可以为一组用户共享
44/58