信息安全数学基础习题集一.doc

学习资料收集于网络，仅供参考 信息安全数学基础-习题集一一、 填空题1、设a=18、b=12，c=27，求a、b、c的最小公倍数a,b,c= .2、求欧拉函数(3000)= .3、设m=9，则模m的最小非负简化剩余系= .4、设m=11，则模m的所有平方剩余= .5、设m=22 ，则模m的所有原根个数= .6. 设m，n是互素的两个正整数，则(mn)=_。7. 设m是正整数，a是满足 ma的整数，则一次同余式：axb (mod m)有解的充分必要条件是_ 。8. 设 m 是一个正整数，a是满足_的整数，则存在整数a，1am ，使得aa1 (mod m)。9. 设aZ, (a,m)=1, 如果同余方程x2a(mod m)_, 则a叫做模m的平方剩余.10. 设a,mZ, m1, (a,m)=1, 则使得ae1(modm)成立的最小正整数e叫做a对模m的_.二、判断题（在题目后面的括号中，对的画“”，错的画“”）1、若k是任意正整数, 则(ak,bk)=(a,b). （ ）2、设a1,a2,an是n个不全为零的整数，则a1,a2,an与a1, |a2|, |a3|, |an|的公因数相同 （ ）3、设m是正整数, 若mab, 则ma或mb. （ ）4、设m为正整数, a,b为整数, ab(modm), db 且d0, 则 adbd(modmd). （ ）5、1,-3,8,4,-10是模5的一个完全剩余系. （ ）6、设m是素数, 模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等. （ ）7、设p=17为奇素数, 模p的平方剩余和平方非剩余的数量各为8.（ ）8、一次同余方程9x1(mod 24)有解.（ ）9、设p是素数, g是模p的原根, 若gx1(modp), 则x是p-1的整数倍. （ ）10、设m1, (a,m)=1, 则1=a0, a, a2, , aordma-1构成模m的简化剩余系. （ ）11. b0, 则(0,b)|b|. （ ）12. 设a,b是两个互素正整数, 那么am, bm, 则 abm. （ ）13. 设m是一个正整数, a,b,d都不为0，若adbd(modm)。则ab(mod m)。（ ）14. 设m为正整数, a是满足(a, m)=1的整数，b为整数. 若r1, r2, r(m)为模m的一个简化剩余系, 则ar1+b,ar2+b, arm+b也为模m的一个简化剩余系. （ ）15. p为素数,n为整数且与p互素，则n2为模p的平方剩余. （ ）16. 设p为正整数, 设aZ, (a,p)=1, 则a是模p的平方剩余的充要条件是: ap+121(mod p). （ ）17. 3是模7的原根。 （ ）18. 设a,mZ, m1, (a,m)=1, d为正整数, 若ad1(modm)，则ordma|d. （ ）19. 整数集关于整数的乘法构成群。 （ ）20. 适当定义加法和乘法，集合0,1可以构成一个有限域。 （ ）三、单项选择题（把答案写在题目后面的括号中）1. 设a与b是两个整数, 则存在整数s,t, 使得a,b=sa+tb，下面关于a与b线性组合描述错误的是：（ ）A. 整数s,t的取值仅有一组唯一的值；B. 整数a,b的线性和所能表示的最小的正整数是a,b最大公因数，即sa+tb=(a,b)；C. a,b的倍数也可以用a,b的线性和表示；D. 整数s,t，可以使用辗转相除法(欧几里得算法)反推得到。2、下面关于整除的描述错误的是：（ ）A. 1是任何整数的因子；B. 设a, bZ（整数集合）, c0 c|b, c|a, 则c|ab；C. 0是任何整数的倍数；D. 设a, bZ, 若 b|a, b0，则b|-a, -b|-a。3、下面的说法正确的是：（ ）A. 给定一个正整数m和两个整数a, b，若ab(modm)，则(a-b)|mB. 设a,b为整数, 若ab(modmi),(i=1,2,k)，则 ab(modm1,m2,mk)；C. 设m1, m2是两个正整数, 若x1, x2分别遍历m1, m2的完全剩余系, 则m2x1+m1x2遍历模m1m2的完全剩余系；D. 设p为素数, a为任意正整数, 则a p-11(modp)。4. 下面哪个集合是模12的简化剩余系？ ( )。 A. 1,3,5,7 B. 1,5,7,9,C. 1,5,7,11 D. 3,5,7,11。 5. 一次同余方程31000x9(mod27)的解数是 （ ）A. 3 B. 2 C. 1 D. 0 6、下面的说法正确的是： （ ）A. 一次同余方程21x55(mod77)有解；B、一次同余方程x6(mod15)，等价于求解一次同余方程组: x2(mod3)x3(mod5) 的解；C、一次同余方程组 x5 (mod13)x20 (mod23)有且仅有唯一的解；D. 设bi, mi是正整数, 对于一次同余方程组xbi(modmi),i=1,2,3, 若(bi, mi)=1, 则同余方程组一定有解。7、设p是奇素数, (a1,p)=1, (a2,p)=1,则下列说法错误的是: （ ）A. 如果a1是模p的平方剩余, a2是模p的平方非剩余, 则a1a2是模p的平方剩余.B. 如果a1是模p的平方剩余, a2是模p的平方非剩余, 则a1a2是模p的平方非剩余.C. 如果a1, a2都是模p的平方剩余, 则a1a2是模p的平方剩余.D. 如果a1, a2都是模p的平方非剩余, 则a1a2是模p的平方剩余.8、下面说法，错误的是（ ）A、设p为奇素数，设aZ, (a,p)=1, 若ap-12-1(mod p)， 方程 x2a(modp)方程肯定无解；B、设p,q是奇素数, 整数a, b, p, q两两互素. 若a既是模p的平方剩余也是模q的平方剩余，则a不是模pq的平方剩余；C、设p,q是奇素数, 整数a, b, p, q两两互素. 若a既是模p的平方剩余也是模q的平方剩余, b既不是模p的平方剩余也不是模q的平方剩余，则ab不是模p的平方剩余；D、设p, q是奇素数, （ab, pq）=1, 只有x2ab(modp)和x2ab(modq)同时有解，对于二次方程x2ab(modpq)才有解。9、已知5对模17的阶为16, 558(mod17), 求ord17(8)的值是（ ）A、2 B、4 C、6 D、810、下面说法错误的是（ ）A、设n是一个正合数, Zn=0,1,2,3, n-1, 则集合Zn0对于乘法: ab=abmodn构成一个交换群；B、设n是一个正整数, 令Z=,-n,-2,-1,0,1,2,n, 即Z是所有整数的集合. 对于通常意义的加法(+)，Z是一个交换群；C、设p是一个素数, Fp=Z/pZ=0,1,2,3, p-1, F*=Fp0, F*是模p的最小非负简化剩余系. 则集合F*对于乘法:ab=abmodp构成一个交换群；D、设n是一个奇素数, Zn=0,1,2,3, n-1, 则集合Zn0对于乘法: ab=abmodn构成一个有限域。11设a, b, c是三个整数，c0且c|a，c|b，如果存在整数s, t, 使得satb1，则 ( ) 。 A. (a, b)= c B. c1 C. csatb D. c1 12. 设a, b, c是三个不全为零的整数。如果 a = bq + c, 其中q是整数，则有( )。 A. (a, b) = (q, c) B. (a, b) = (b, c) C. (a, b) = c D. (a, b) = (a, c)13. 下面哪个集合不是模5的一个完全剩余系？ ( ) 。 A. 1, 3, 5, 7,9 B. 2,4,6,8,10C. 0, 1, 2,11,13 D. 0, 1, 2, 13, 19。 14. 下面哪个集合是模18的简化剩余系？ ( )。 A. -1, 5, 7, 11, 13, 17 B. -1, 5, 9, 11, 13, 15,17C. -5, 1, 5, 7, 11,17 D. 1, 3, 5, 7, 9.11, 13, 17。 15. 满足5618 (modm)的正整数m(m2)的个数是( )。 A. 1 B. 2 C. 4 D. 516. 30模23的逆元是 ( ) 。 A. 23 B. 19 C. 10 D. 4 17. 下列一次同余式无解的是( )。 A. 12x3（mod 16） B. 8x9（mod 19），C. 78x30（mod 98） D. 111x6（mod 51）。18. 下面哪个是模13的平方剩余? ( )。 A. 5 B. 10 C. 11 D. 7 19下面各组数中，均为模14的原根的是( )。 A. 2, 3, 4, 5 B. 3, 6, 8, 10 C. 9, 11, 13 D. 3, 5 20. 定义运算：ab=abmod12, 下面哪个集合构成一个群.（ ）A. 1,2,3,4 B. 1,3,5,7 C. 1,5,7,9 D. 1,5,7,11四、简答题1. 设a=15,b=101,求整数s,t, 使得as+tb=(a,b). （给出具体求解过程）2. 设a,mZ, m1, (a,m)=1, d为正整数, 则ad1(modm)的充分必要条件是ordma|d. 给出充分性的证明.3. 计算71005(mod 15)。（给出具体求解过程，提示：可用欧拉定理或也可中国剩余定理进行求解）4. 求7模26的阶ord26(7)，并给出所有模26的阶为ord26(7)的整数g（1g26）。（给出具体求解过程）5. 判断同余方程x23(mod 11)的解的情况。（给出具体求解过程）6. 设n是一个正合数, Zn=0,1,2,3, n-1, 令Zn*=(Z/nZ)*=a|aZn,(a,n)=1, 也即模n的最小非负简化剩余系. 则集合Zn*对于乘法: ab=abmodn是否构成一个交换群？（请给出详细求解判断过程）7. a42，b164，求a和b的最大公因子（a，b）及整数x和y，使（a, b）axby.8. 证明：设m为正整数, a,b为整数, adbd(modm). 若(d,m)=1, 则ab(modm).9. 结合欧拉定理和模重复平方算法(或者平方乘算法)计算62025（mod41）10. 写出模17的所有平方剩余。11. 计算5模19的指数ord19(5)。12. 设不可约多项式fx=x2+x+1，集合G=x01, x1x, x2 x+1 . 若定义乘法:ab=ab(modf(x)，根据群的定义，判断G, 是否构成一个群。五、综合题（备注，每题必须给出具体求解过程）1. 解一次同余方程 175x410817(mod 133).2. 由GF(2)上的4次不可约多项式fx=x4+x3+1构成有限域GF(24)，GF(24)中16个域元素，0除外，其余元素可用x的幂次方来表示: x01, x1x, x2x2 , x3x3x4（ ） x5x3+x+1, x6（ ）, x7x2+x+1, x8x3+x2+x, x9（ ）, x10x3+x, x11x3+x2+1,x12x+1, x13x2+x, x14x3+x2 , x15（ ）（1）完成上面的填空（4分）。x4 .x6 x9 x15 (2)已知h(x)= x2+1, g(x)=x3+x2+1是GF(24)中的多项式并根据上面的结果计算（1） 求hxg(x) （2） 求hxg(x) （3） 求h(x)-1(modfx) （4） 求g(x)-1(modfx) 3、求解一次同余方程 84x+164(mod 371).信息安全数学基础-习题集一答案第一题填空1、108 2、800 3、1,2,4,5,7,8 4、1,3,4,5,9 5、46、(m)(n) 7、(a,m)|b 8、(a,m)=1 9、有解 10、阶二、判断题15： 6-10： 1115： 16-20： 三、单项选择题1-5：ACBCD 6-10：CABDA11-15：DBCCB 16-20：CABDD四、简答题1、101=156+11 15=11+4 11=42+3 4=31+1 因此(a,b)=（101,15）=1 1=4-3=4-(11-42)=43-11=(15-11)3-11=153-114=153-(101-156)4=1527-1014 因此s=27 ，t=-4 备注：s=27 t=-4不是唯一答案，只要满足as+tb=(a,b) 都正确 2、证明: 充分性. 由条件ordma|d ，证明ad1(modm) 设ordma|d, 则存在整数k, 使得d=kordma, 从而adakordma(aordma)k 1(modm). 3、解：71005(mod 15)，已知（7,15）=1，由欧拉定理7（15）1(mod15)，781(mod15) 因此7100571005（mod 8） 75 (mod 15) 72 4 (mod 15) 74 1 (mod 15) 757 (mod 15) 因此 710057(mod 15) 备注：此计算方法不是唯一，也可以用中国剩余定理化简求解4、（1）已知26=213，26 =12。 （2）7223-3(mod26)，73-215(mod26) 7625-1(mod26) ，7是模26的一个原根, ord26(7)=12 因为模12的简化剩余系为1,5,7,11, 故模26的所有原根为: 717, 7511, 77-33-719, 711-7*9 -1115 (mod 26).即模26的原根为:7,11,19,15 5、解：判断同余方程x23(mod 11)的解的情况根据欧拉判别式进行求解进行判断 311-1235121(mod 11) 即3是模11的平方剩余，即x23(mod 11)方程有解 备注：判断x23(mod 11)方程解情况也可采用0,1,.,5代入方程穷举方法求解。6、设n是一个正合数, Zn=0,1,2,3, n-1, 令Zn*=(Z/nZ)*=a|aZn,(a,n)=1, 也即模n的最小非负简化剩余系. 则集合Zn*对于乘法: ab=abmod n是否构成一个交换群. (1) 封闭性. 对任意a,bZn*, 恒有ab(modn)Zn*. (2) 结合律成立. 对任意a,b,cG, 有(ab)c=a(bc). (3) 恒等元存在, 恒等元e=1. 即对任意aZn*, 有eZn*, 使ae=ea=a. (4)对任意aZn*, 则(a,n)=1，因此存在a的逆元 a-1Zn*, 使a a-1= a-1a=e. 显然, 乘法满足交换律, 故该群是交换群.7、164=423+38 42=38+4 38=49+2 4=22 因此(a,b)=（166,42）=2 2=38-49=38-(42-38) 9=3810-429=(164-423)10-429=16410-4239 备注：不是唯一答案，只要满足as+tb=(a,b) 都正确 8、证明: 证明: 由 adbd(modm)可得 mad-bd=(a-b)d. 而(d,m)=1, 故m(a-b), 即 ab(modm). 9、解：62017（mod41），已知（6,41）=1，由欧拉定理6（41）1(mod41)，6401(mod41) 因此62017（mod41）617（mod41） 62 -5 (mod 41) 64 -16 (mod 41) 6810 (mod 41) 61618 (mod 41) 因此 6201718626(mod 41) 10、1,224(mod 17), 329(mod 17), 4216(mod 17), 528(mod 17), 622(mod 17), 7215(mod 17)，8213(mod 17)，模17的所有平方剩余为1，2，4，8，9，13，15，16 11、19=18 526(mod19)，5311(mod19)，567(mod19)，591(mod19) (4分)ord19(5)=9 12、(1)封闭性满足 (2)结合律满足 (3)单位元为1 (4)因为1，x，x+1都与fx互素，故逆元都存在 G, 构成一个群。五、综合题（备注，每题必须给出具体求解过程）1. 解一次同余方程 175x410817(mod 133).解：（1）首先方程可以进行化简（175 mod 133）x42x410817 (mod 133)（42,133）=（67,719）=7，7|410817，因此方程有解，有7个解 （2）(133)=618=108, 41081(mod 133)，因此41081(mod 133)4因此同余方程175x410817 (mod 133)等价于 42x4