信息安全数学基础考试复习题 - 图文

第一章

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））=2 32 运用广义欧几里得除法求整数s，t使得sa+tb=(a,b) (1) 1613,3589

3589=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）=1

1=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,3772

50 求最小公倍数

（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=539 51 求最大公因数与最小公倍数 （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*13 60 求7x+4y=100的整数解

解：因为 (7,4)|100 所以该方程有解

当x=4，y=18时，7x+4y=100成立 所以方程的整数解为

X=4-4t t=0,+1,+ -2,…… y=18+7t

第二章

6 2008年5月9日是星期五，问第220080509天是星期几？

8 设p是素数，证明：如果a2≡b2(mod p) 则p|a-b或p|a+b

10 设整数a,b,c(c>0),满足a≡b(mod c),求证：（a,c）=(b,c)

16 计算2(mod 47)，2（mod 47），2(mod 47)

解：1）设m=47，b=2，令a=1，将32写成二进制 32=25 n0=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）

32

47

200

24 计算 3（mod 7）

6

解：因为3≡1 mod 7 所以31000000=36*166666+4（mod 7）≡34（mod 7）≡4（mod 7） 35 证明：如果p和q是不同的素数，则pq - 1+qp - 1≡1(mod pq) 1000000

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）的一个特解x0≡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’=1 M2=2*5*7=70 M2’M2≡1mod 3 →M2’=1 M3=2*3*7=42 M3’M3≡1mod 5 →M3’=1 M4=2*3*5=30 M4’M4≡1mod 7 →M4’=4 X=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=[(mod 101) j yj ]=10 0 1 1 2 2 4 3 8 4 16 5 32 6 64 7 27 8 54 9 7 y=3穷搜： i 0 1 2 3 4 5 6 …… y*2-pi 3 94 50 18 59 98 7 …… 所以y*2-10*6 ≡29→3=269→log23=69

本文来源：https://www.bwwdw.com/article/hay2.html