《数论算法》教案 5章(原根与离散对数)

《数论算法》 第五章 原根与离散对数

（3）恰有

??m?2x2?a?modm?有解。

个整数a，对模互不同余，且使得方程

27． 设整数m＞2，整数a满足?a,m?＝1，且设同余方程x2?a?modm?有解。证明该方程恰有两个解的充分必要条件是m有一个原根。

28． 请构造以10为底对模61的离散对数表。

29． 判断下列方程是否有解，若有解，请求其解： （1）x22≡5（mod 41）； （2）x22≡29（mod 41）； （3）x22≡5（mod 61）； （4）x22≡29（mod 61）。 30． 构造相应的对数表，并利用其解下列同余方程： （1）3x6≡5（mod 7）； （2）5x12≡12（mod 17）； （3）3x15≡13（mod 23）； （4）5x27≡22（mod 31）。 31． 解同余方程： （1）x6≡－15（mod 64）； （2）x12≡7（mod 128）； 32． 利用对数表解同余方程： （1）x40≡85（mod 98＝2?72）； （2）x80≡501（mod 686＝2?73）； （3）x27≡663（mod 1058＝2?232）（已知5是模数23

的原根）。 33． 解同余方程：

（1）3x6≡7（mod 25?31）； （2）5x4≡3（mod

； 25?23?19）

34． 对哪些整数b，同余方程7x8?b（mod 41）可解？ 35． 设素数p＞2。证明：同余方程 x4??1?modp?有解的充分必要条件是p?1?mod8?。由此推出形如p≡1（mod 8）的素数有无穷多个。

36． 设p为素数，证明：同余方程x8?16?modp?一定有解。

37． 利用原根求出以下模m的全部3次、4次剩余：

m＝13, 17, 19, 23, 41, 43, 172, 232, 412, 432 38． 证明：2是模73的8次剩余。 39． 设素数p≡3（mod 4）。证明：a是模p的4次剩余的充分必要条件是?a?≡1，即a是模p的二次剩余。

?p?57/58

??《数论算法》 第五章 原根与离散对数

40． 利用对数表或求离散对数的方法解下列同余方程： （1）3x≡2（mod 23）； （2）9?10x≡62（mod 229）； （3）3x≡64（mod 161）； （4）3?5x≡67（mod 119）。

58/58