信息安全数学基础习题集一
- 格式：docx
- 大小：29.67 KB
- 文档页数：10
下载文档原格式
合集下载
信息安全数学基础考试复习题
信息安全数学基础考试复习题第⼀章27 证明：如果整数a,b,c是互素且⾮零的整数，那么（ab,c)=(a,b)(a,c)证明：由题(a,b)=1=(a,c), 因为a,b,c 互素，所以（ab,1）=1, 所以（ab,c)=(a,b)(a,c)28 求最⼤公约数（1）（55,85）解：85=55*1+30 55=30*1+25 25=5*5 所以（55,85）=5（2）（202,282）解：282=202*1+80 202=80*2+42 80=42*1+38 42+38*1+4 38=4*9+2 4=2*2 所以（202,282）=2 29 求最⼤公因数（1）（2t-1,2t+1）解：2t+1=（2t-1）*1+2 2t-1=2*（t-1）+1 t-1=（t-1）*1 所以（2t-1,2t+1）=1（2）（2n，2（n+1））解： 2（n+1）=2n*1+2 2n=2*n 所以（2n，2（n+1））=232 运⽤⼴义欧⼏⾥得除法求整数s，t使得sa+tb=(a,b)(1)1613,35893589=1613*2+363 1613=363*4+161 363=161*2+41 161=41*3+38 41=38*+3 38=3*12+2 3=2*1+1 2=1*1+1所以（1613,3589）=11=3-1*2=3-1*（38-3*12）=14*4-14*（161-3*41）= - 14*161+55*（363 - 2*161）=55*363+（-124）*（1613 - 4*363）=(-124)*1613+551*(3589 – 2*1613)=551*3589+(-1226)*1613所以S=-1226 t=551(2)2947,377250 求最⼩公倍数（1）8,60（3）49,77解：77=49*1+28 49=28*1+21 28=21*1+7 21=7*3 所以（49，77）=7所以[49,77]=49*77/7=53951 求最⼤公因数与最⼩公倍数（1）22335577,27355372解：所以（22335577,27355372）=22335372 [22335577,27355372]=27355577（2）23571113，2*3*5*7*11*13解：（23571113，2*3*5*7*11*13）=2*5*7[23571113，2*3*5*7*11*13]=23*3*57*7*113*1360 求7x+4y=100的整数解解：因为 (7,4)|100 所以该⽅程有解当x=4，y=18时，7x+4y=100成⽴所以⽅程的整数解为X=4-4t t=0,+1,+ -2,……y=18+7t6 2008年5⽉9⽇是星期五，问第220080509天是星期⼏？8 设p是素数，证明：如果a2≡b2(mod p) 则p|a-b或p|a+b10 设整数a,b,c(c>0),满⾜a≡b(mod c),求证：（a,c）=(b,c)16 计算232(mod 47)，247（mod 47），2200(mod 47)解：1）设m=47，b=2，令a=1，将32写成⼆进制 32=25n0=0，a0=a=1 b1=b2≡4(mod 47)n1=0，a1=a0=1 b2=b12≡16(mod 47)n2=0，a2=a1=1 b3=b22≡21(mod 47)n3=0，a3=a2=1 b4=b32≡18(mod 47)n4=0，a4=a3=1 b5=b42≡42(mod 47)n5=1，a5=a4*b5≡42(mod 47)2)由费马⼩定理得247≡2(mod 47)3)2200=24*47+12(mod 47)=216(mod 47)=18(mod 47)22 运⽤wilson定理，求8*9*10*11*12*13（mod 7）24 计算 31000000（mod 7）解：因为36≡1 mod 7 所以31000000=36*166666+4（mod 7）≡34（mod 7）≡4（mod 7）35 证明：如果p和q是不同的素数，则p q - 1+q p - 1≡1(mod pq)36 证明：如果m和n是互素的整数，则mΨ(n)+nΨ(m)≡1(mod mn)1 求求出下列⼀次同余⽅程的所有解（1）3x≡2（mod 7）（2）6x≡3（mod 9）解：因为（6,9）=313 所以原同余式有解同余式6x≡3（mod 9）的⼀个特解x≡2（mod 9）所以所有解为x≡2+3t（mod 9） t=0,1,2 即x≡2,5,8（mod 9）8 求11的倍数，使得该数被2,3,5,7除的余数为1解：由题意得：x≡1 mod 2 x≡1 mod 3 x≡1 mod 5 x≡1 mod 7 x=11k①M=2*3*5*7=210 M1=3*5*7=105 M1’M1≡1mod 2 →M1’=1M2=2*5*7=70 M2’M2≡1mod 3 →M2’=1M3=2*3*7=42 M3’M3≡1mod 5 →M3’=1M4=2*3*5=30 M4’M4≡1mod 7 →M4’=4X=105*1*1+70*1*1+42*3*1+3*4*1(mod 210)≡1②由①②得x=2101……解⾮唯⼀第四章10 计算下列勒让德符号1）（17/37） 2)(151/373) 3)(191/397) 4)(911/2003)16 判断下列同余⽅程是否有解1）x2≡7（mod 227）25 求所有素数p使得与5为模p的⼆次剩余解：由题意得：x2≡5（mod p）因为5/p=(-1)(5-1)(p-1)/(2*2)*(p/5)=(-1)p-1(p/5)所以当p=2时，（5/2）=(1/2)=1 即p=2成⽴当p=3时，（5/3）=(2/3)= - 1,即p=3不成⽴所以p=2.连分数连分数定理使⽤Shanks⼩步⼤步法计算离散对数2是F101的⼀个本原元，在F101中求log23解：m=[]=10。
信息安全数学基础第一章-第1章习题解答
39 设a, b 是任意两个不全为零的整数，
(i) 若m是任一整数，则[am, bm]＝[a, b]m。
(ii) [a, 0]＝0 。
证明:(i) 设 L＝ [a, b]，则 a L， b L，进而
am Lm， bm Lm，即Lm是am, bm的公倍数。
所以[am, bm] Lm＝ [a, b]m。
所以a (2j－i－1) ，但 j－i < d0，得到矛盾。
说明
r1, r2 ,
,
rd
0
互不相同。
1
从而，1, r1 1, r2 1, , rd0 1 1
是2d 被 a 除后，d0个不同的最小非负余数。 最后，由
2d0 s 1 2d0 2s 2s 2s 1 2s (2d0 1) (2s 1)
37 设a, b 是两个不同的整数，证明如果整数n > 1 满足n|(a2－b2) 和 n | (a＋b)，n | (a－b)，则n是合数。 证明：由已知及a2－b2＝(a＋b)(a－b)得
n|(a＋b)(a－b)。 若 n 是素数，根据1.4定理2, n|(a＋b) 或 n|(a－b)， 与已知条件矛盾。所以n是合数。
(an , b)＝(aan－1 , b)＝(an－1 , b)＝(aan－2 , b) ＝ (an－2 , b)＝…＝ (a2 , b)＝(aa , b)＝ (a , b)＝ 1
(b，an) ＝(an , b)＝1，类似的
(bn , an)＝(bbn－1 , an)＝(bn－1 , an)＝(bbn－2 , an)
21 证明：n >1 时， 1＋ 1 ＋1＋ ＋ 1 不是整数。
23
n
1 通分后，2 这一项的分子变为奇数k，其余各项的
信息安全数学基础课后答案完整版Word版
第一章参考答案（1） 5,4,1,5.（2） 100=22*52, 3288=23*3*137.（4） a,b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs,又因为(a,b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子相乘a n=(p1p2––pr)n, b n=(q1q2––qs)n明显a n, b n也没有公共(相同)素因子.（5）同样将a, b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs,a n=(p1p2––pr)n, b n=(q1q2––qs)n,因为a n| b n所以对任意的i有, pi的n次方| b n,所以b n中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b.（6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2––pr,b=q1q2––qs, ab=p1p2––prq1q2––qs, 又因为a, b, c互素, 所以a, b, c中没有公共(相同)素因子, 明显ab和c也没有公共(相同)素因子.所以(ab, c)= (a, b)(a, c).（7）2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,9 7,101,103,107, 109, 113, 127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199.（11）对两式进行变形有21=0(mod m), 1001=0(mod m),可以看出要求满足的m即使求21和1001的公约数, 为7和1.（12）(70!)/(61!)= 62*63*––*70=(-9)*(-8)*––*(-1)=-9!=-362880=1(mod 71). 明显61!与71互素, 所以两边同乘以61!, 所以70!=61!(mod 71).（13）当n为奇数时2n=(-1)n=-1=2(mod 3), 两边同时加上1有2n+1=0(mod 3), 所以结论成立.当n为偶数时2n=(-1)n=1(mod 3), 两边同时加上1有2n+1=2(mod 3), 所以结论成立.（14）第一个问：因为(c,m)=d, m/d为整数.假设ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r所以ac=bc(mod m/d),因为(c,m/d)=1,所以两边可以同除以一个c, 所以结论成立.第二个问题：因为a=b(mod m), 所以a-b=ki *mi，a-b是任意mi的倍数，所以a-b是mi 公倍数，所以[mi]|a-b.(利用式子：最小公倍数=每个数的乘积/最大公约数, 是错误的, 该式子在两个数时才成立)（15）将整数每位数的值相加, 和能被3整除则整数能被3整除, 和能被9整除则整数能被9整除, (1)能被3整除, 不能被9整除，(2)都不能，(3)都不能，(4)都不能第二章答案（5）证明：显然在群中单位元e满足方程x2=x, 假设存在一个元素a满足方程x2=x, 则有a2=a, 两边同乘以a-1有a=e. 所以在群中只有单位元满足方程x2=x.（6）证明：因为群G中每个元素都满足方程x2=e, 所以对群中任意元素a,b 有aa=e, bb=e, (ab)2=abab=e. 对abab=e, 方程两边左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以G是交换群.（7）证明：充分性：因为在群中对任意元素a,b有(ab)2=a2b2即abab=aabb, 方程两边左乘以a的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以G是交换群.必要性：因为群G是交换群, 所以对任意元素a,b有ab=ba, 方程两边左乘以a右乘以b有abab=aabb, 有(ab)2=a2b2.（8）证明：因为xaaba=xbc，所以x-1xaxbaa-1b-1=x-1xbca-1b-1，所以存在唯一解x=a-1bca-1b-1使得方程成立。
信息安全数学基础习题答案
信息安全数学基础习题答案信息安全数学基础习题答案1.简答题 a) 什么是信息安全？信息安全是指保护信息的机密性、完整性和可用性，以防止未经授权的访问、使用、披露、干扰、破坏或篡改信息的行为。
b) 什么是加密？加密是指通过对信息进行转换，使其无法被未经授权的人理解或使用的过程。
加密算法通常使用密钥来对信息进行加密和解密。
c) 什么是对称加密算法？对称加密算法是一种使用相同的密钥进行加密和解密的算法。
常见的对称加密算法有DES、AES等。
d) 什么是非对称加密算法？非对称加密算法是一种使用不同的密钥进行加密和解密的算法。
常见的非对称加密算法有RSA、ECC等。
e) 什么是哈希函数？哈希函数是一种将任意长度的数据映射为固定长度的输出的函数。
哈希函数具有单向性，即很难从哈希值逆推出原始数据。
2.选择题 a) 下列哪种算法是对称加密算法？ A. RSA B. AES C. ECC D.SHA-256答案：B. AESb) 下列哪种算法是非对称加密算法？ A. DES B. AES C. RSA D. SHA-256答案：C. RSAc) 下列哪种函数是哈希函数？ A. RSA B. AES C. ECC D. SHA-256答案：D. SHA-2563.计算题 a) 使用AES算法对明文进行加密，密钥长度为128位，明文长度为64位。
请计算加密后的密文长度。
答案：由于AES算法使用的是128位的块加密，所以加密后的密文长度也为128位。
b) 使用RSA算法对明文进行加密，密钥长度为1024位，明文长度为64位。
请计算加密后的密文长度。
答案：由于RSA算法使用的是非对称加密，加密后的密文长度取决于密钥长度。
根据经验公式，RSA算法中加密后的密文长度为密钥长度的一半。
所以加密后的密文长度为1024/2=512位。
c) 使用SHA-256哈希函数对一个长度为128位的明文进行哈希计算，请计算哈希值的长度。
答案：SHA-256哈希函数的输出长度为256位。
信息安全数学基础习题答案
信息安全数学基础习题答案信息安全数学基础习题答案第⼀章整数的可除性1．证明：因为2|n 所以n=2k , k∈Z5|n 所以5|2k ，⼜（5，2）=1，所以5|k 即k=5 k1，k1∈Z7|n 所以7|2*5 k1 ,⼜（7，10）=1，所以7| k1即k1=7 k2，k2∈Z 所以n=2*5*7 k2即n=70 k2, k2∈Z 因此70|n2．证明：因为a3-a=(a-1)a(a+1)当a=3k，k∈Z 3|a 则3|a3-a当a=3k-1，k∈Z 3|a+1 则3|a3-a当a=3k+1，k∈Z 3|a-1 则3|a3-a所以a3-a能被3整除。
3．证明：任意奇整数可表⽰为2 k0+1，k0∈Z（2 k0+1）2＝4 k02+4 k0+1=4 k0 (k0+1)+1由于k0与k0+1为两连续整数，必有⼀个为偶数，所以k0 (k0+1)=2k所以（2 k0+1）2=8k+1 得证。
4．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a3-a由第⼆题结论3|（a3-a）即3|(a-1)a(a+1)⼜三个连续整数中必有⾄少⼀个为偶数，则2|(a-1)a(a+1)⼜（3，2）=1 所以6|(a-1)a(a+1) 得证。
5．证明：构造下列k个连续正整数列：(k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k∈Z对数列中任⼀数 (k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1], i=2,3,4,…(k+1)所以i|(k+1)！+i 即(k+1)！+i为合数所以此k个连续正整数都是合数。
6．证明：因为1911/2＜14 ,⼩于14的素数有2，3，5，7，11，13经验算都不能整除191 所以191为素数。
因为5471/2＜24 ,⼩于24的素数有2，3，5，7，11，13，17，19，23经验算都不能整除547 所以547为素数。
信息安全数学基础习题答案
4
21．解： （1）因为 875961*2753≡[(36mod9)(17mod9)]mod9 ≡0(mod9) 2410520633≡26(mod9) ≡8(mod9) 所以等式 875961*2753=2410520633 不成立 （2）因为 14789*23567≡[(29mod9)(23mod9)]mod9 ≡1(mod9) 348532367≡41(mod9) ≡5(mod9) 所以等式 14789*23567=348532367 不成立 （3）因为 24789*43717≡[(30mod9)(22mod9)]mod9 ≡3(mod9) 1092700713≡30(mod9) ≡3(mod9) 所以等式 24789*43717=1092700713 可能成立 （4）这种判断对于判断等式不成立时简单明了，但对于判断等式成立时，可能会较 复杂。 22．解：因为 7 为素数，由 Wilso 定理知：(7-1)! ≡-1(mod7) 即 6！≡-1（mod7） 所以 8*9*10*11*12*13≡1*2*3*4*5*6(mod7) ≡6!(mod7) ≡-1(mod7) 31．证明：因为 c1,c2,…,c ϕ (m)是模 m 的简化剩余系 对于任一 ci，有 m-ci 也属于模 m 的简化剩余系 所以 ci+(m-ci)≡0(modm) 因此 c1+c2+…+c ϕ (m)≡0(modm) 32．证明：因为 a ϕ (m)≡1(modm) 所以 a ϕ (m)-1≡0(modm) a ϕ (m)-1=(a-1)(1+a+ a2+…+ a ϕ (m)-1) ≡0(modm) 又（a-1,m）=1 所以 1+a+ a2+…+ a ϕ (m)-1 ≡0(modm) 33．证明：因为 7 为素数，由 Fermat 定理知 a7 ≡a(mod7) 又（ a ，3 ） =1 所以 (a,9)=1 由 Euler 定理 知 a ϕ (9) ≡ a6 ≡ 1(mod9) a(mod9) 又(7,9)=1, 所以 a7≡a(mod7*9) 即 a7≡a(mod63) 34．证明：因为 32760=23*32*5*7*13 又(a,32760)=1 所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1 有：a ϕ (13)≡1(mod13) 即 a12≡1(mod13) a ϕ (8)≡a4≡1(mod8) 即 a12≡1(mod8) a ϕ (5)≡a4≡1(mod5) 即 a12≡1(mod5) a ϕ (7)≡a6≡1(mod7) 即 a12≡1(mod7) a ϕ (9)≡a6≡1(mod9) 即 a12≡1(mod9) 又因为[5,7,8,9,13]=32760 所以 a12≡1(mod32760) 35．证明：因为(p,q)=1 p,q 都为素数 所以 ϕ (p)=p-1, ϕ (q)=q-1 由 Euler 定理知：p ϕ (q)≡1(modq) q ϕ (p)≡1(modp) 即 pq-1≡1(modq) qp-1≡1(modp) 又 qp-1≡0(modq) pq-1≡0(modp) 所以 pq-1+qp-1≡1(modq) qp-1+pq-1≡1(modp) 又[p,q]=pq 所以 pq-1+qp-1≡1(modpq) 36．证明：因为(m,n)=1 由 Euler 定理知：m ϕ (n)≡1(modn) n ϕ (m)≡1(modm) 所以 m ϕ (n)+n ϕ (m)≡(m ϕ (n)modn)+ (n ϕ (m)modn)≡1+0≡1(modn)
信息安全数学基础习题集一
信息安全数学基础习题集一信息安全数学基础----习题集一一、填空题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是满足m?a的整数，则一次同余式：ax≡b (mod m)有解的充分必要条件是_________________ 。
8. 设 m 是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m ，使得aa’≡1 (mod m)。
9. 设a∈Z,(a,m)=1, 如果同余方程x2≡a(mod m)__________, 则a 叫做模m的平方剩余.10. 设a,m∈Z,m>1,(a,m)=1, 则使得a e≡1(mo d m)成立的最小正整数e叫做a 对模m的__________.二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）1、若k是任意正整数, 则(ak,bk)=(a,b). （）2、设a1,a2,…,a n是n个不全为零的整数，则a1,a2,…,a n与a1, |a2|, |a3|,…, |a n|的公因数相同（）3、设m是正整数, 若m│ab, 则m│a或m│b. （）4、设m为正整数, a,b为整数, a≡b(mod m), d│b且d>0, 则ad ≡bd(mod md).（）5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）6、设m是素数, 模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等. （）7、设p=17为奇素数, 模p的平方剩余和平方非剩余的数量各为8. （）8、一次同余方程9x≡1(mod 24)有解. （）9、设p是素数, g是模p的原根, 若g x≡1(mod p), 则x是p?1的整数倍.（）10、设m>1,(a,m)=1, 则1=a0,a,a2, …, a ord m(a)?1构成模m 的简化剩余系.（）11. b≠0, 则(0,b)＝|b|. （）12. 设a,b是两个互素正整数, 那么a│m,b│m, 则ab│m. （）13. 设m是一个正整数, a,b,d都不为0，若ad≡bd(modm)。
《信息安全数学基础》部分课后习题答案
《信息安全数学基础》课后作业及答案第1章课后作业答案 (2)第2章课后作业答案 (6)第3章课后作业答案 (13)第4章课后作业答案 (21)第5章课后作业答案 (24)第6章课后作业答案 (27)第7章课后作业答案 (33)第8章课后作业答案 (36)第9章课后作业答案 (40)第10章课后作业答案 (44)第11章课后作业答案 (46)第12章课后作业答案 (49)第13章课后作业答案 (52)第1章课后作业答案习题1：2, 3, 8(1), 11, 17, 21, 24, 25, 312. 证明：存在整数k，使得5 | 2k + 1，并尝试给出整数k的一般形式。
证明k = 2时，满足5 | 2k + 1。
5 | 2k + 1，当且仅当存2k + 1 = 5q。
k, q为整数。
即k = (5q– 1)/2。
只要q为奇数上式即成立，即q = 2t + 1，t为整数即，k = 5t + 2，t为整数。
3. 证明：3 3k + 2，其中k为整数。
证明因为3 | 3k，如果3 | 3k + 2，则得到3 | 2，矛盾。
所以，3 3k + 2。
8. 使用辗转相除法计算整数x, y，使得xa + yb = (a, b)：(1) (489, 357)。
解489 = 357×1 + 132,357 =132 × 2 + 93,132 = 93 × 1 + 39,93 = 39 × 2 + 15,39 = 15 × 2 + 9,15 = 9 × 1 + 6,9 = 6 × 1 + 3,6 = 3 × 2 + 0,所以，(489, 357) = 3。
132 = 489 – 357×1,93 = 357 – 132 × 2 = 357 – (489 – 357×1) × 2 = 3 × 357 – 2 ×489,39 = 132 – 93 × 1 = (489 – 357×1) – (3 × 357 – 2 ×489) × 1 = 3 ×489 – 4× 357,15 = 93 – 39 × 2 = (3 × 357 – 2 × 489) – (3 ×489 – 4× 357) × 2 = 11× 357 – 8 × 489,9 = 39 – 15 × 2 = (3 ×489 – 4× 357) – (11× 357 – 8 × 489) × 2 = 19 × 489 – 26× 357,6 = 15 – 9 × 1 = (11× 357 –8 × 489) – (19 × 489 – 26× 357) = 37 ×357 – 27 × 489,3 = 9 – 6 × 1 = (19 × 489 – 26× 357) – (37 × 357 – 27 × 489) = 46 ×489 – 63 × 357。
信息安全数学基础(许春香)习题答案
第一章（1）5,4,1,5.（2）100=22*52, 3288=23*3*137.（4）多种解法，其中一种：a,b可以表示成多个素因子的乘积a=p1p2––p r, b=q1q2––q s,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子相乘a n=(p1p2––p r)n, b n=(q1q2––q s)n明显a n, b n也没有公共(相同)素因子.（5）多种解法，其中一种：由算术基本定理：a,b可分解为有限个素数的乘积，得：a=p1^r1*p2^r2*……*pn^rn, b= p1^r1’*p2^r2’*……*pn^rn’,若a|b不成立，则存在素数pi使得pi在a中的幂ri大于pi在b中的幂ri‘，即：ri>ri’a^n=p1^r1n*p2^r2n*…*pi^rin*…*pn^rnn, b^n= p1^r1’n*p2^r2’n*…* pi^ri’n *…*pn^rn’n,则ri*n>ri’*n，所以a^n|b^n不成立。
（6）多种解法，其中一种：由于a,b,c互素且非零所以(a,b)=1,(b,c)=1所以存在u,v,r,s使ua+vc=1，rb+sc=1两式相乘得：(ur)ab+(usa+vrb+vsc)c=1所以(ab,c)=(a,b)(a,c)=1（7）2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107, 109, 113, 127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199.（11）对两式进行变形有21=0(mod m), 1001=0(mod m),可以看出要求满足的m即使求21和1001的公约数, 为7和1.（12）多种解法，其中一种：70！=(70*69*68*67*66*65*64*63*62)*61!70*69*68*67*66*65*64*63*62≡(-1)(-2)…(-9) (mod71) ≡1mod71所以70！≡61!（13）多种解法，其中一种：当n是奇数时，不妨设n=2k+1,k为整数则2^n+1≡(-1)^(2k+1)+1≡0(mod3)当n是偶数时，不妨设n=2k,k为整数则2^n+1≡(-1)^(2k)+1≡2(mod3)综上，n是奇数时，3整除2^n+1，n是偶数时，3不整除2^n+1（14）第一个问题：因为(c,m)=d.假设ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r 所以ac=bc(mod m/d),因为(c,m/d)=1,所以两边可以同除以一个c, 所以结论成立.第二个问题：因为a=b(mod m), 所以a-b=k i*m i，a-b是任意m i的倍数，所以a-b是m i公倍数，所以[m i]|a-b.（15）将整数每位数的值相加, 和能被3整除则整数能被3整除, 和能被9整除则整数能被9整除, (1)能被3整除, 不能被9整除，(2)都不能，(3)都不能，(4)都不能常见问题：1.写出构成群和不构成群的原因13.证明ab-1∈A∩B即可14.用群的定义证明(题意是证明映射后的集合为一个群)第二章1.判断方法：分别验证1.对运算是否封闭,2.对任意的a, b, c是否满足结合律,3.对任意a是否存在单位元,4.对任意a是否存在逆元. 可以得出在(1)-(10)中(2),(3),(6), (7) (10)构成群(1)不满足结合律，不存在逆元, (4)不存在单位元(5)不满足结合律(8)不构成，不存在逆元(9)不构成，不存在逆元2. a-b-c≠a-(b-c)，所以不构成，不满足结合律5．证明：显然在群中单位元e满足方程x2=x, 假设存在一个元素a满足方程x2=x, 则有a2=a, 两边同乘以a-1有a=e. 所以在群中只有单位元满足方程x2=x.6．证明：因为群G中每个元素都满足方程x2=e, 所以对群中任意元素a,b有aa=e, bb=e, (ab)2=abab=e. 对abab=e, 方程两边左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以G是交换群.7．证明：充分性：因为在群中对任意元素a,b有(ab)2=a2b2即abab=aabb, 方程两边左乘以a 的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以G是交换群.必要性：因为群G是交换群, 所以对任意元素a,b有ab=ba, 方程两边左乘以a右乘以b 有abab=aabb, 有(ab)2=a2b2.8．证明：方程xaxba=xbc两边同时左乘a-1x-1,右乘a-1b-1有a-1x-1xaxbaa-1b-1=a-1x-1xbc a-1b-1，化简得x=a-1bc a-1b-1，可知方程有解。
信息安全数学基础试卷一
《信息安全数学基础》试卷一一、判断题（本题满分10分，共含10道小题，每小题1分，认为命题正确的请在答题表里填写“√”，认为命题错误的请在答题表里填写“×”）1、任何一个交换群必定是循环群。
2、若4mod b a ≡，则有8mod b a ≡。
3、若无向图中的每一对顶点之间都有链，则此无向图为树。
4、存在一个无向图G ，G 既是哈密顿图，又是欧拉图。
5、若G H ≤1，G H ≤2，则G H H ≤⋂21。
6、同余方程 有解 。
7、模n 的缩系中共有)1(-n ϕ个元素。
8、),,⨯+Z （是一个域。
9、对于奇素数p 而言，模p 的两个二次剩余之积为二次剩余，两个二次非剩余之积为二次剩余。
10、对称群3S 有4阶子群。
二、计算题（本题满分15分）1、设T 是一棵无向树且有3个次数是3的点,2个次数是2的点,其余均为次数是1的点，求出该树一共有多少个点？（本小题5分）2、使用扩展的Euclid 算法求解(a,b)及整数s ，t,使得sa+tb=(a,b),其中a=135,b=97。
（本小题10分）三、解答题（本题满分45分）1、利用整数的惟一分解定理求出(45，100)和[45，100]。
（本小题6分）2、写出模7的缩同余类集合，列出其乘法运算表，并求出此集合中所有非零元素关于乘法的逆元。
（本小题15分）3、判断下列二次同余方程是否有解，并给出判断依据。
（本小题15分） （1） （2）)137(mod 62=x )365(mod 12-=x (mod )k x a n ≡⇔(,())|g k n ind a ϕ4、有向图如图1所示，写出其对应的邻接矩阵、关联矩阵，并判断此图是否为连通图，给出判断依据。
（本小题9分）图1四、求解下列同余方程或同余方程组 （本题满分15分）1、)15(mod 93≡x （本小题5分）2、⎪⎩⎪⎨⎧≡≡≡9mod 711mod 57mod 2x x x （本小题10分）五、证明题（本题满分15分）1、证明：若n b a mod ≡，n d c mod ≡，则有n d b c a mod +≡+。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
信息安全数学基础----习题集一一、填空题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是满足mm的整数，则一次同余式：ax≡b(modm)有解的充分必要条件是_________________。
8.设m是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m，使得aa’≡1(modm)。
9.设m∈m,(m,m)=1,如果同余方程m2≡m(mod m)__________,则m叫做模m 的平方剩余.10.设m,m∈m,m>1,(m,m)=1,则使得m m≡1(mod m)成立的最小正整数m叫做m对模m的__________.二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）1、若m是任意正整数,则(mm,mm)=(m,m). （）2、设m1,m2,…,m m是m个不全为零的整数，则m1,m2,…,m m与m1,|m2|,|m3|,…,|m m|的公因数相同（）3、设m是正整数,若m│mm,则m│m或m│m.（）4、设m为正整数,m,m为整数,m≡m(mod m),m│m且m>0,则mm ≡mm(mod mm).（）5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）6、设m是素数,模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等.（）7、设m=17为奇素数,模m的平方剩余和平方非剩余的数量各为8. （）8、一次同余方程9m≡1(mod24)有解. （）9、设m是素数,m是模m的原根,若m m≡1(mod m),则m是m−1的整数倍.（）10、设m>1,(m,m)=1,则1=m0,m,m2,…,m ord m(m)−1构成模m的简化剩余系.（）11.m≠0,则(0,m)＝|m|.（）12.设m,m是两个互素正整数,那么m│m,m│m,则mm│m.（）13.设m是一个正整数,a,b,d都不为0，若ad≡bd(modm)。
则a≡b(modm)。
（）14.设m为正整数,a是满足(m,m)=1的整数，b为整数.若m1,m2,…,m m(m)为模m 的一个简化剩余系,则mm1+b,mm2+b,…,mm m(m)+b也为模m的一个简化剩余系.（）15.p为素数,n为整数且与p互素，则n2为模p的平方剩余.（）16.设m为正整数,设m∈m,(m,m)=1,则m是模m的平方剩余的充要条件是:m m+12≡1(mod m).（）17.3是模7的原根。
（）18.设m,m∈m,m>1,(m,m)=1,m为正整数,若m m≡1(mod m)，则ord m(m)|m.（）19.整数集关于整数的乘法构成群。
（）20.适当定义加法和乘法，集合{0,1}可以构成一个有限域。
（）三、单项选择题（把答案写在题目后面的括号中）1.设m与m是两个整数,则存在整数m,m,使得(m,m)=mm+mm，下面关于m与m线性组合描述错误的是：（）A.整数m,m的取值仅有一组唯一的值；B.整数m,m的线性和所能表示的最小的正整数是m,m最大公因数，即mm+mm= (m,m)；C.(m,m)的倍数也可以用m,m的线性和表示；D.整数m,m，可以使用辗转相除法(欧几里得算法)反推得到。
2、下面关于整除的描述错误的是：（）A.±1是任何整数的因子；B.设m,m∈m（整数集合）,c≠0m|m,m|m,则m|m±m；C.0是任何整数的倍数；D.设m,m∈m,若m|m,m≠0，则m|−m,−m|−m。
3、下面的说法正确的是：（）A.给定一个正整数m和两个整数m,m，若m≡m(mod m)，则(m−m)|mB.设m,m为整数,若m≡m(mod m m),(m=1,2,…,m)，则m≡m(mod[m1,m2,…,m m])；C.设m1,m2是两个正整数,若m1,m2分别遍历m1,m2的完全剩余系,则m2m1+ m1m2遍历模m1m2的完全剩余系；D.设m为素数,m为任意正整数,则m m−1≡1(mod m)。
4.下面哪个集合是模12的简化剩余系？()。
A.1,3,5,7B.1,5,7,9,C.1,5,7,11D.3,5,7,11。
5.一次同余方程31000m≡9(mod27)的解数是（）A.3B.2C.1D.06、下面的说法正确的是：（）A.一次同余方程21x≡55(mod77)有解；B、一次同余方程m≡6(mod15)，等价于求解一次同余方程组:{m≡2(mod3)m≡3(mod5)的解；C、一次同余方程组{m≡5 (mod13)m≡20 (mod23)有且仅有唯一的解；D.设m m,m m是正整数,对于一次同余方程组m≡m m(mod m m),m=1,2,3,若(m m,m m)=1,则同余方程组一定有解。
7、设m是奇素数,(m1,m)=1,(m2,m)=1,则下列说法错误的是:（）A.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方剩余.B.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方非剩余.C.如果m1,m2都是模m的平方剩余,则m1m2是模m的平方剩余.D.如果m1,m2都是模m的平方非剩余,则m1m2是模m的平方剩余.8、下面说法，错误的是（）A、设p为奇素数，设m∈m,(m,m)=1,若m m−12≡−1(mod m)，方程m2≡m(mod m)方程肯定无解；B、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余，则m不是模mm的平方剩余；C、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余,m既不是模m的平方剩余也不是模m的平方剩余，则mm不是模m的平方剩余；D、设m,m是奇素数,（mm,mm）=1,只有m2≡mm(mod m))和m2≡mm(mod m)同时有解，对于二次方程m2≡mm(mod mm)才有解。
9、已知5对模17的阶为16,5×5≡8(mod17),求ord17(8)的值是（）A、2B、4C、6D、810、下面说法错误的是（）A、设m是一个正合数,m m={0,1,2,3,…,m−1},则集合m m\{0}对于乘法:mm=m×m(mod m)构成一个交换群；B、设m是一个正整数,令m={…,−m,…,−2,−1,0,1,2,…,m,…},即m是所有整数的集合.对于通常意义的加法(+)，m是一个交换群；C、设m是一个素数,m m=m/mm={0,1,2,3,…,m−1},m∗=m m\{0},m∗是模m的最小非负简化剩余系.则集合m∗对于乘法:mm=m×m(mod m)构成一个交换群；D、设m是一个奇素数,m m={0,1,2,3,…,m−1},则集合m m\{0}对于乘法:mm=m×m(mod m)构成一个有限域。
11．设a,b,c是三个整数，c≠0且c|a，c|b，如果存在整数s,t,使得sa＋tb＝1，则()。
A.(a,b)=cB.c＝1C.c＝sa＋tbD.c＝±112.设a,b,c是三个不全为零的整数。
如果a=bq+c,其中q是整数，则有()。
A.(a,b)=(q,c)B.(a,b)=(b,c)C.(a,b)=cD.(a,b)=(a,c)13.下面哪个集合不是模5的一个完全剩余系？()。
A.1,3,5,7,9B.2,4,6,8,10C.0,1,2,11,13D.0,1,2,13,19。
14.下面哪个集合是模18的简化剩余系？()。
A.-1,5,7,11,13,17B.-1,5,9,11,13,15,17C.-5,1,5,7,11,17D.1,3,5,7,9.11,13,17。
15.满足56≡18(modm)的正整数m(m>2)的个数是()。
A.1B.2C.4D.516.30模23的逆元是()。
A.23B.19C.10D.417.下列一次同余式无解的是()。
A.12x≡3（mod16）B.8x≡9（mod19），C.78x≡30（mod98）D.111x≡6（mod51）。
18.下面哪个是模13的平方剩余()。
A.5B.10C.11D.719．下面各组数中，均为模14的原根的是()。
A.2,3,4,5B.3,6,8,10C.9,11,13D.3,520.定义运算：mm=m×m(mod12),下面哪个集合构成一个群.（）A.{1,2,3,4}B.{1,3,5,7}C.{1,,5,7,9}D.{1,5,7,11}四、简答题1.设m=15,m=101,求整数m,m,使得mm+mm=(m,m).（给出具体求解过程）2.设m,m∈m,m>1,(m,m)=1,m为正整数,则m m≡1(mod m)的充分必要条件是ord m(m)|m.给出充分性的证明.3.计算71005(mod15)。
（给出具体求解过程，提示：可用欧拉定理或也可中国剩余定理进行求解）4.求7模26的阶ord26(7)，并给出所有模26的阶为ord26(7)的整数g（1<g<26）。
（给出具体求解过程）5.判断同余方程x2≡3(mod11)的解的情况。
（给出具体求解过程）6.设m是一个正合数,m m={0,1,2,3,…,m−1},令m m∗=(m/mm)∗={m|m∈m m,(m,m)=1},也即模m的最小非负简化剩余系.则集合m m∗对于乘法:mm=m×m(mmmm)是否构成一个交换群？（请给出详细求解判断过程）7.a＝42，b＝164，求a和b的最大公因子（a，b）及整数x和y，使（a,b）＝ax＋by.8.证明：设m为正整数,m,m为整数,mm≡mm(mod m).若(m,m)=1,则m≡m(mod m).9.结合欧拉定理和模重复平方算法(或者平方乘算法)计算62025（mod41）10.写出模17的所有平方剩余。
11.计算5模19的指数ord19(5)。
12.设不可约多项式m(m)=m2+m+1，集合G={m0≡1,m1≡m,m2≡m+1}.若定义乘法:mm=m×m(mmmm(m))，根据群的定义，判断{G,}是否构成一个群。
五、综合题（备注，每题必须给出具体求解过程）1.解一次同余方程175x≡41081×7(mod133).2.由GF(2)上的4次不可约多项式m(m)=m4+m3+1构成有限域mm(24)，GF(24)中16个域元素，0除外，其余元素可用m的幂次方来表示:m0≡1,m1≡m,m2≡m2,m3≡m3m4≡（）m5≡m3+m+1,m6≡（）,m7≡m2+m+1,m8≡m3+m2+m,m9≡（）,m10≡m3+m,m11≡m3+m2+1, m12≡m+1, m13≡m2+m,m14≡m3+m2 ,m15≡（）（1）完成上面的填空（4分）。