一、判断题
1. 设p是素数,g是模p的原根,若g x≡1(mod p),则x是p的整数倍. （×）
2. 设m是正整数, (a,m)=1,若x d≡1(mod m),则d|φ(m). （×）
3. 只有m是素数时,模m的原根才存在. （×）
4. 根据费马小定理, 26≡1(mod7),故ord7(2)=6. （×）
5. 若y≡g x(mod p), 则x≡ind g y(mod y).（×）
二、综合题
1. 已知6是模41的原根, 9=630,求ord41(9).
解：6是模41的原根因此可知φ(41)=40, 0≡1 (mod 41)9≡630(mod 41)
1≡(0)3≡(630)4(mod 41),因此ord41(9)=4
2. 写出模5的全部原根.
解：5是素数，肯定有原根，原根个数φ(φ(5))=φ(4)=2. 5是比较小素数，因此可以用穷举方法进行求解原根
5的简化剩余系为{1,2,3,4,}，且计算可得
11≡1;
21≡2, 22≡4, 23≡3, 24≡1;
31≡3, 32≡4, 33≡2, 34≡1;
41≡4, 42≡1;
因此根据原根定义，可知2和3是模5的原根。
3. 已知模22的原根存在,求出模22的所有原根.
解：22=2*11，满足2pα形式，原根肯定存在。原根个数为φ(φ(22))=φ(10)=4=22的素因数只有q=2,
φ(m)
=φ(22)
=5
根据定理5.8.1，故只需计算g5模p=22是否同余1.
先判断g=2是否为模22的原根，因25(mod22)≢1. 所以2模22的原根. 因此模22的所有原根2d,其中d为模10的简化剩余系{1,3,7,9}。模22的所有原根为：
21≡2, 23≡8, 27≡18, 29≡6 (mod 22).
即模22的所有4个原根为:2,8,18,6
4. 已知5对模17的阶为16, 列出所有模17阶为8的整数a(0解：φ(17)=16, 516 ≡1(mod 17)。 ord 17(a)=8，即 a 8≡1(mod 17) a 8≡1≡516 ≡(52)8(mod 17) 5是模17的原根，ord 17(5)=16，因此ord 17(52)=8 根据下面性质： 设a,b,m ∈Z,(a,m)=1, （1）若b ≡a(mod m), 则ord m (b )=ord m (a ). 8≡25(mod 17) , ord 17(52) =ord 17(8) 即模17阶为8的整数为8 再根据下面性质： 设a,b,m ∈Z,(a,m)=1, （2）ord m (a −1)=ord m (a ). 可知ord 17(8−1)=ord 17(8)，因此 8−1=−2≡15(mod 17) 因此ord 17(8−1)=ord 17(15)=ord 17(8)=8 因此 所有模17阶为8的整数a 为8和15 5. 已知m =133的原根存在, 求模m 的原根有多少个？ 解：原根个数为φ(φ(133))=φ(133×(1− 113))=φ(132×12)=φ(132×22×3)=132× 22×3×(1−113)(1−12)(1−13)=624 6. 模101的原根个数有多少个？ 解：原根个数为φ(φ(101))=φ(100)=φ(22×52)=100×(1−12)(1−15 )=40 7. 已知ord 41(18)=5, 快速求1818(mod41). 解：ord 41(18)=5，185≡1（mod 41） 1818≡185*3+3 ≡183 ≡183 (mod41) ≡182 ×18≡37 ×18≡10(mod41) 8. 编程实现寻找某个整数的原根. 略 1. 描述群的定义. 参见书本88页，定义6.1.4 2. 描述域的定义. 参见书本95页6.3.1 域的定义 3. 找出在F2[x]上，所有最高次数为5的不可约多项式. 解：最高次数为5的多项式总共包括32个多项式，这32个多项式中,不可约多项式为x5+x3+1，x5+x3+x2+x+1，x5+x2+1，x5+x，x5+x4+x2+x+1, x5+x4+ x3+x+1, x5+x4+x3+x2+1 4. 已知x4+x+1是F2[x]中的不可约多项式, F2[x]/ x4+x+1的余式构成一个有限域 F. 回答下列问题: （1）这个有限域中, 加法单位元和乘法单位元各是什么？ （2）在域F上计算(x2+1)×(x3 +1). （3）在域F上计算(x2)−1(mod x4+x+1). 解：（1）加法零元为0，乘法单位元为1 （2）(x2+1)×(x3 +1)= x5 +x3+x2+1≡x(x4+x+1 )+x3+x+1(mod( x4+ x+1))≡x3+x+1 (3) 用欧几里得扩展算法x4+x+1=x2×x2+(x+1) x2=x(x+1)+x (x+1)=x+1 1=(x+1)−x=(x+1)−(x2-x(x+1))=−x2+(x+1)(x+1)=−x2+(x+1)(x4+x+1−x2×x2)=(x+1)(x4+x+1)- x2((x+1)x2+1)两边同时模x4+x+1 1≡− x2((x+1)x2+1) (x2)−1(mod x4+x+1)≡−((x+1)x2+1)≡x3+x2+1 5. 已知g(x)=x4+x+1是F2[x]中的不可约多项式, 从而F2[x]/(x4+x+1)是一个域. 求f(x), 使得f(x)×x3≡1(mod g(x)). 解：求x3模g(x)的逆元 (x4+x+1)=x×x3+(x+1) x3=(x2+x)(x+1)+x (x+1)=x+1 1=(x+1)−x=(x+1)−(x3−(x2+x)(x+1))=−x3+(x+1)(1+(x2+x)) =−x3+(1+x2+x)((x4+x+1)−(x×x3))=(1+x2+x)(x4+x+1)−x3(1+ x(1+x2+x)) 两边同时模g(x)可得： 1≡−x3(1+x(1+x2+x))≡−x3(1+x+x3+x2)≡x3(1+x+x3+x2) 因此f(x)=(1+x+x3+x2)（ mod g(x))6. 编程实现F2[x]上两个多项式相乘. 略 7. 编程实现多项式的带余除法. 略下载本文
