《数论算法》 第五章 原根与离散对数
若有解，请求其解。
dlog17,52??17?＝16，（解）查表6.3.2知dlog17,510≡7，≡6，??17?,dlog17,510＝（16, 7）＝1，显然方程有解。 由例6.1.4知5是17的一个原根，对方程两边取以5为
底的对数
xdlog510?dlog52?mod??17??
即
7x≡6（mod 16）
解之得x?10?mod16?，即为原方程的解。
【例6.6.5】判断幂同余方程4x≡16（mod 17）是否有解，若有解，请求其解。
（解）查表6.3.2得dlog17,54≡12，dlog17,516≡8，（16, 12）＝4，且48?dlog17,516，所以方程有解。对方程两边取以5为底的对数得一次同余方程
12x≡8（mod 16）
解之得x≡2, 6, 10, 14（mod 16），即为原方程的解。
比较例6.6.4和例6.6.5，一个为单解，一个为多解，其本质原因在于指数函数10x的底数10是17的原根，故对应真数2，使得10x≡2（mod 17）成立的模16不同余的x只能有一个，而后者中函数4x的底数4不是原根，其对模数17的阶为ord17?4?＝4，故对模数4来说，其解为1；而对模数16来说，其不同余的解则为4个。
??5.7 单向函数
(一) 单向函数
（1）给定x，计算y＝f(x)是容易的； （2）给定y， 计算x＝f?1?y?是不可行的。
53/58
《数论算法》 第五章 原根与离散对数
例如：对给定的g，已知x，计算y≡gx mod n容易；
但已知y，计算x≡logg(y)（mod ??n?）则很难。 (二) 单向陷门函数
（1）已知陷门k和x，则计算y＝f(x)容易； （2）已知y，但不知k，则计算x＝fk?1?y?是不可行的；
（3）已知k和y， 则计算x＝fk?1?y?容易。
例如，对于RSA算法，计算y≡xe（mod n）容易；若
已知d和y，计算x≡yd（mod n）也很容易；但若
不知d，则无法计算x≡ey（mod n）。
(三) 构造公钥密码体制的关键
寻找合适的单向陷门函数。
习题5
1． 设m＝12, 13, 14, 19, 20, 21： （1）列出模m的阶数表；
（2）如果模m有原根，请找出模m的最小正剩余系中的
所有原根，即模m的最小正原根；
（3）若模m没有原根，请找出模m的最小正剩余系中所
有对模m的阶为最大的整数。
2． 求ord41(10)，ord43(7)，ord55(2)，ord65(8)，ord91(11)，ord69(4)，ord231(5)。
3． 设m＝37, 43。求出模m的最小正剩余系中所有阶为6的整数。
4． 证明：设p为素数，ordp?a?＝3，则ordp?1?a?＝6。 5． 证明：若存在整数a且有ordm?a?＝m－1，则m是素数。
6． 设p为素数，ordp?a??k。证明：
54/58
《数论算法》 第五章 原根与离散对数
（1）若2k，则ak2≡－1（mod （2）若4k，则ordp??a??k； （3）若2k，4
； p）
k，则ordp??a??k2
7． 设m＞1为整数，?a,m?＝1。证明：若ordm?a??st，
则ordm?as??t。
8． 设m是一个正整数，d是??m?的一个正因数。问是否存在整数a，满足ordm?a??d。
9． 设m＞1，d?1，?a,m?＝1，并设ordm?ad??e。试决定ordm?a?的值应满足的条件，以及其可能取值的个数。
10． 设a和n均为正整数且m?an?1。证明：ordm?a??n，从而进一步说明n??m?。
11． 设m＞1，?ab,m?＝1，并设?ordm?a?,ordm?b???d。证明：
（1）d2ordm??ab?d??ordm?a?ordm?b?；
（2）d2ordm?ab???ordm?ab?,d?ordm?a?ordm?b?。
12． 针对每个p，试求一个g，它是模p的原根，但不是模p2的原根。其中p＝5, 7, 11, 17, 31。
13． 证明：10是487的原根，但不是4872的原根。 14． 针对每个p，求模p的所有原根g（1＜g＜p）。其中p＝19, 31, 37, 53, 71。
15． 针对每个p，求模2p的所有原根g（1＜g＜p）。其中p＝19, 31, 37, 53, 71。
16． 针对每个p，试求一个g，对所有??1，它是p?和2p?的原根。其中p＝11, 13, 17, 19, 31, 37, 53, 71。
17． 若m有原根g，并设1?k???m?，证明：?k,??m??＝1。是两两对模m不同余的模m的全部原根，其个数为????m??。
18． 设m?1，n?1，且?n,??m???1。证明：当x遍历模
gkm的既约剩余系时，xn也遍历模m的既约剩余系。
19． 设Fn?22?1为第n个Fermat数。证明：
n（1）ordF?2??2n?1；
（2）若素数pFn，则ordp?2??2n?1；
n55/58
《数论算法》 第五章 原根与离散对数
（3）Fn的素因数q?1?mod2n?1?；
（4）若Fn是素数，n＞1，则2一定不是Fn的原根； （5）若Fn是素数，则模Fn的任一二次非剩余必是Fn的原
根；
（6）若Fn是素数，则±3, ±7都是其原根。
20． 设p, q是素数，证明以下结论，并分别针对每种情形举出两个实例以验证结论：
（1）若q≡1（mod 4），p?2q?1，则2是模p的原根； （2）若q≡－1（mod 4），p?2q?1，则－2是模p的原
根；
（3）若q≡1（mod 2）且q＞3，p?2q?1，则－3，－4
都是模p的原根； （4）若q≡1（mod 2），p?4q?1，则2是模p的原根。 21． 设素数p＞3，g1,g2,?,g??p?1?是模数p的??p?1?个原根，证明
??p?1?i?1?gi?1?modp?
22． 设正整数m≠3, 4, 6且其全部非负最小正原根为
g1,g2,?,gk。证明：?gi?1?modm?。
i?1k23． 已知10是61的一个原根，请利用10找出61的所有原根。
24． 设g是奇素数p的一个原根，证明： （1）当p≡1（mod 4），－g也是p的一个原根；
p?1。 225． 证明：若p?2n?1且为素数（n＞1），则3是p的一
（2）当p≡3（mod 4），－g对模p的阶为
个原根。
26． 设整数m＞2且有原根，整数a满足?a,m?＝1。证明：
（1）同余方程x2?a?modm?有解的充分必要条件是
??m?a2?1?modm?；
（2）方程x2?a?modm?若有解，则恰有两个解；
56/58