信息安全数学基础习题答案
信息安全数学基础习题答案
第一章整数的可除性
1．证明：因为2|n 所以n=2k , k∈Z
5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z
7|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|n
2．证明：因为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为素数。
由737=11*67 ,747=3*249 知737与747都为合数。
8．解：存在。eg：a=6,b=2,c=9
10．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈N+
又p1≤p2≤p3，所以n= p1 p2 p3k≥p13 即p13≤n1/3
p1为素数则p1≥2，又p1≤p2≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p22
即p2≤(n/2)1/2得证。
11．解：小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：
12．证明：反证法
假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相
乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个3k+1的素数相乘，得
到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。
同理可证其他。
13．证明：反证法
假设形如4k+3的素数只有有限个，记为p1, p2,…, p n
因为4k+3=4k`-1=4k-1 构造N=4*p1*p2*…*p n-1≥3*p1*p2*…*p n
所以N＞p i (i=1,2,…,n)
N为4k-1形式的素数，即为4k+3的形式，所以假设不成立。
原结论正确，形如4k+3的素数有无穷多个。
28．（1）解：85=1*55+30
55=1*30+25
30=1*25+5
25=5*5
所以(55,85)=5
（2）解：282=1*202+80
202=2*80+42
80=1*42+38
42=1*38+4
38=9*4+2
4=2*2
所以（202,282）=2
29．（1）解：2t+1=1*(2t-1)+2
2t-1=(t-1)*2+1
2=2*1
所以（2t+1,2t-1）=1
（2）解：2(n+1)=1*2n+2
2n=n*2
所以（2n,2(n+1)）=2
32．（1）解：1=3-1*2
=3-1*(38-12*3)
=-38+13*(41-1*38)
=13*41-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）解：1=4-1*3
=4-1*(115-28*4)
=-115+29*(119-1*115)
=29*119+(-30)*(353-2*119)
=-30*353+89*(472-1*353)
=89*472+(-119)*(825-1*472)
=(-119)*825+208*(2947-3*825)
=208*2947+(-743)*(3772-1*2947)
=951*2947+(-743)*3772
所以s=951 t=-743
36．证明：因为（a，4）=2 所以a=2*(2m+1) m∈Z
所以a+b=4m+2+4n+2=4(m+n)+4=4(m+n+1)
即4|a+b
所以（a+b,4）=4
37．证明：反证法
假设n为素数，则n| a2- b2=(a+b)(a-b)
由1.4定理2知n|a+b或n|a-b,与已知条件矛盾
所以假设不成立，原结论正确，n为合数。
40．证明：（1）假设是21/2有理数，则存在正整数p，q，使得21/2=p/q,且（p, q）=1 平方得：p2=2q2, 即2|p2，所以p=2m, m∈N
因此p2=4m2=2q2 q2=2m2 q=2n, n∈N
则（p, q）=(2m,2n)=2(m, n)≥2与（p, q）=1矛盾
所以假设不成立，原结论正确，21/2不是有理数。
（2）假设是71/2有理数，则存在正整数m，n，使得71/2=m/n,且（m, n）=1 平方得：m2=7n2, 即7|m2
将m表示成n个素数p i的乘积，m= p1 p2 p3……p n ，p i为素数。
因为7为素数，假设7 !| m，则7 !∈｛p1，p2，p3，……p n｝
所以m2= p12 p22 p32……p n 2=( p1 p2 p3……p n)( p1 p2 p3……p n)
所以7 !| m2，与7|m2矛盾，故7|m, m=7k
同理可知：7|n, n=7 k0
所以(m, n)=(7k,7 k0)=7(k, k0)≥7 与已知矛盾
故原结论正确，71/2不是有理数。
（3）同理可证171/2不是有理数。
41．证明：假设log210是有理数，则存在正整数p, q,使得log210=p/q,且（p, q）=1 又log210=ln10/ln2=p/q
Ln10q=ln2p 10q=2p
(2*5)q=2p 5q=2p-q
所以只有当q=p=0是成立，所以假设不成立
故原结论正确，log210是无理数。
同理可证log37，log1521都是无理数。
50．（1）解：因为8=23, 60=22*3*5
所以[8,60]=23*3*5=120
51．（4）解：(471179111011001,4111831111011000)= 4104707908301011000=1011000
[471179111011001,4111831111011000]= 4111471179111831111011001
第二章．同余
1．解：（1）其中之一为9，19，11，21，13，23，15，25，17
（2）其中之一为0，10，20，30，40，50，60，70，80
（3）.（1）或（2）中的要求对模10不能实现。
2．证明：当m>2时，因为(m-1)2=m2-2m+1=m(m-2)+1
所以(m-1)2≡1(mod m)
即1与(m-1)2在同一个剩余类中，故02,12,…,(m-1)2一定不是模m的完全剩余系。6．解：21≡2(mod7), 22≡4(mod7), 23≡1(mod7)
又20080509=6693503*3
所以220080509=(23)6693503≡1(mod7)
故220080509是星期六。
7．证明：（i）因为a i≡b i (modm),1≤i≤k 所以a i=b i+k i m
又a1+a2+… +a k=∑a i=∑(b i+k i m)=∑b i+m*∑k i
所以有∑a i≡∑b i (mod m)
即a1+a2+… +a k=b1+b2+… +b k (mod m)
（ii）因为a i≡b i (mod m),1≤i≤k 所以a i(mod m)=b i (mod m)
所以（a1a2…a k）mod m≡[(a1mod m)( a2mod m)…(a k mod m)]mod m
≡[(b1mod m)( b2mod m)…(b k mod m)]mod m
≡（b1b2…b k）mod m
所以a1a2…a k≡a1a2…a k(mod m)
8．证明：如果a2≡b2(mod p) 则a2= b2+kp , k∈Z
即kp=a2-b2=(a+b)(a-b) 所以p|(a+b)(a-b)
又p为素数，根据1.4定理2知p|a+b或p|a-b 得证。
9．证明：如果a2≡b2(mod n) 则a2= b2+kn , k∈Z
即kn=a2-b2=(a+b)(a-b) 所以n|(a+b)(a-b)
由n=pq知kpq=a2-b2=(a+b)(a-b)
因为n!|a-b, n!|a+b，所以p,q不能同时为a-b或a+b的素因数。
不妨设p|a-b, q|a+b ,则q!|a-b, p!|a+b 即(q, a-b)=1,(p, a+b)=1
因此(n, a-b)=(pq, a-b)=(p, a-b)=p>1
(n, a+b)=(pq, a+b)=(q, a+b)=q>1
故原命题成立。
10．证明：因为a≡b (mod c) 则a=cq+b , q∈Z
根据1.3定理3知(a, c)=(b, c)
17．解：（1）a k+a k-1+… +a0=1+8+4+3+5+8+1=30
因为3|30 ,9!|30 所以1843581能被3整除，不能被9整除。
（2）a k+a k-1+… +a0=1+8+4+2+3+4+0+8+1=31
因为3!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。
（3）a k+a k-1+… +a0=8+9+3+7+7+5+2+7+4+4=56
因为3!|56 , 9!|56 所以8937752744不能被3整除，也不能被9整除。
（4）a k+a k-1+… +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58
因为3!|58 , 9!|58 所以4153768912246不能被3整除，也不能被9整除。20．解：（89878*58965）mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9
≡6(mod9) ≡5299?56270(mod9)
又5299?56270≡(45+?)mod9≡?(mod9)
所以 ?=6 即未知数字为6。
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．证明：因为c 1,c 2,…,c ?(m)是模m 的简化剩余系
对于任一c i ，有m-c i 也属于模m 的简化剩余系
所以c i +(m-c i )≡0(modm)
因此c 1+c 2+…+c ?(m)≡0(modm)
32．证明：因为a ?(m)≡1(modm) 所以a ?(m)-1≡0(modm)
a ?(m)-1=(a-1)(1+a+ a 2+…+ a ?(m)-1) ≡0(modm)
又（a-1,m ）=1
所以1+a+ a 2+…+ a ?(m)-1 ≡0(modm)
33．证明：因为7为素数，由Fermat 定理知a 7
≡a(mod7)
又（a ，3）=1 所以(a,9)=1 由Euler 定理知a ?(9)≡a 6≡1(mod9) 即a 7≡a(mod9)
又(7,9)=1, 所以a 7≡a(mod7*9)
即a 7≡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) 即a 12≡1(mod13)
a ?(8)≡a 4≡1(mod8) 即a 12≡1(mod8)
a ?(5)≡a 4≡1(mod5) 即a 12≡1(mod5)
a ?(7)≡a 6≡1(mod7) 即a 12≡1(mod7)
a ?(9)≡a 6≡1(mod9) 即a 12≡1(mod9)
又因为[5,7,8,9,13]=32760
所以a 12≡1(mod32760)
35．证明：因为(p,q)=1 p,q 都为素数 所以?(p)=p-1, ?(q)=q-1 由Euler 定理知：p
?(q)≡1(modq) q ?(p)≡1(modp) 即p q-1≡1(modq) q p-1≡1(modp)
又 q p-1≡0(modq) p q-1≡0(modp)
所以p q-1+q p-1≡1(modq) q p-1+p q-1≡1(modp)
又[p,q]=pq 所以p q-1+q p-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) 同理有：m ?(n)+n ?(m) ≡1(modm)
又[m,n]=mn 所以m ?
(n)+n ?(m) ≡1(modmn)
第三章.同余式
1．（1）解：因为（3，7）=1 | 2 故原同余式有解
又3x ≡1（mod7） 所以 特解x 0`≡5（mod7）
同余式3x ≡2（mod7）的一个特解x 0≡2* x 0`=2*5≡3（mod7）
所有解为：x ≡3（mod7）
（3）解：因为（17，21）=1 | 14 故原同余式有解
又17x ≡1（mod21） 所以 特解x 0`≡5（mod21）
同余式17x ≡14（mod21）的一个特解x 0≡14* x 0`=14*5≡7（mod21）
所有解为：x ≡7（mod21）
2．（1）解：因为（127，1012）=1 | 833 故原同余式有解
又127x ≡1（mod1012） 所以 特解x 0`≡255（mod1012）
同余式127x ≡833（mod1012）的一个特解x 0≡833* x 0`=833*255≡907（mod1012） 所有解为：x ≡907（mod1012）
3．见课本3.2例1
7．（1）解：因为（5，14）=1
由Euler 定理知，同余方程5x ≡3（mod14）的解为：
x ≡5?(14)-1*3≡9（mod14）
（2）解：因为（4，15）=1
由Euler 定理知，同余方程4x ≡7（mod15）的解为：
x ≡4?(15)-1*7≡13（mod15）
（3）解：因为（3，16）=1
由Euler 定理知，同余方程3x ≡5（mod16）的解为：
x ≡3?(16)-1*5≡7（mod16）
11．证明：由中国剩余定理知方程解为：
x ≡a 1M 1M 1`+ a 2M 2M 2`+……+ a k M k M k `（mod m ）
因为m i 两两互素，又中国剩余定理知：M i M i `≡1（mod m i ）
又M i =m/m i 所以（m ，M i ）≡1（mod m i ）
所以M i M i `=M i ?(mi)≡（mod m i ）
代入方程解为x ≡a 1 M 1?(m1)+ a 2 M 2?(m2)+……+ a k M k ?(mk)(mod m) 得证。
12．（1）解：由方程组得：3x+3y ≡2(mod7)
6x+6y ≡4(mod7) x+y ≡-4(mod7)
X ≡5(mod 7) y ≡5 (mod 7)
（2）解：由方程组得：2x+6y ≡2(mod7) 2x-y ≡2(mod7)
6x+8y ≡4(mod7) x-y ≡-4(mod7)
X ≡6(mod 7) y ≡3 (mod 7)
13．见课本3.2例4
14．同课本3.2例3 21000000≡562（mod1309）
15．（1）解：等价同余式组为：
23x ≡1（mod4）
23x≡1（mod5）
23x≡1（mod7）
所以 x≡3（mod4） x≡2（mod5） x≡4（mod7）
所以x≡3*35*3 + 2*28*2 + 4*20*6≡67（mod140）
（2）解：等价同余式组为：
17x≡1（mod4）
17x≡1（mod5）
17x≡1（mod7）
17x≡1（mod11）
所以 x≡1（mod4） x≡2（mod5） x≡-3（mod7） x≡7（mod11）
所以x≡1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 ≡557（mod1540）19．解：3x14+4x13+2x11+x9+x6+x3+12x2+x≡0（mod7）
左边=(x7-x)( 3x7+4x6+2x4+x2+3x+4)+ x6+2x5+2x2+15x2+5x
所以原同余式可化简为：x6+2x5+2x2+15x2+5x≡0（mod7）
直接验算得解为：x≡0（mod7） x≡6（mod7）
20．解：f`(x) ≡ 4x3+7（mod243）
直接验算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）
f`(x1) ≡4*13*7=-1(mod3) f`(x1)-1≡-1(mod3)
所以t1≡-f（x1）*( f`(x1)-1(mod3))/31≡1(mod 3)
x2≡x1+3 t1≡4(mod 9)
t2≡-f（x2）*( f`(x1)-1(mod3))/32≡2(mod 3)
x3≡x2+32 t2≡22(mod 27)
t3≡-f（x3）*( f`(x1)-1(mod3))/33≡0(mod 3)
x4≡x3+33 t3≡22(mod 81)
t5≡-f（x4）*( f`(x1)-1(mod3))/34≡2(mod 3)
x5≡x4+34 t4≡184(mod 243)
所以同余式f（x）≡0(mod243)的解为：x5≡184(mod 243)
第四章．二次同余式与平方剩余
2．解：对x=0,1,2,3,4,5,6时，分别求出y
x=0,y2≡1(mod7),y≡1,6(mod7)
x=4,y2≡4(mod7),y≡2,5(mod7)
当x=1,2,3,5,6时均无解
5．解：对x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16时，分别求出y
x=0,y2≡1(mod17),y≡1,16(mod17)
x=1,y2≡3(mod17),无解
x=2,y2≡11(mod17),无解
x=3,y2≡14(mod17),无解
x=4,y2≡1(mod17),y≡1,16(mod17)
x=5,y2≡12(mod17),无解
x=6,y2≡2(mod17),y≡6,11(mod17)
x=7,y2≡11(mod17),无解
x=8,y2≡11(mod17),无解
x=9,y2≡8(mod17),y≡5,12(mod17)
x=10,y2≡8(mod17),y≡5,12(mod17)
x=11,y2≡0(mod17),y≡0(mod17)
x=12,y2≡7(mod17),无解
x=13,y2≡1(mod17),y≡1,16(mod17)
x=14,y2≡5(mod17),无解
x=15,y2≡8(mod17),y≡5,12(mod17)
x=16,y2≡16(mod17),y≡4,13(mod17)
10．解：(1）.（17/37）=(-1) (17-1)(37-1)/(2*2)*(37/17)=-1
(4）.（911/2003）=(-1) (2003-1)(911-1)/(2*2)*(2003/911)=1/3=1
(6）.（7/20040803）=(-1) (7-1)(20040803-1)/(2*2)*(20040803/7)=1
12．解：（1）.因为（-2/67）=(65/67)=1
所以-2是67的平方剩余
所以x2≡-2(mod67)有2个解。
（4）.因为（2/37）=(-1) (37*37-1)/8=-1
所以2是37的平方非剩余
所以x2≡2(mod37)无解。
14．证明：（1）因为p为其素数，模p的所有二次剩余个数为(p-1)/2个，
设为a1, a2, a3, …a(p-1)/2
则a1*a2*a3…a(p-1)/2≡12*22*32…((p-1)/2)2(mod p)
≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(mod p)
≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(p-1)/2(mod p)
≡(p-1)!*(-1)(p-1)/2(mod p)
≡(-1)*(-1)(p-1)/2(mod p) （2.4定理3）
≡(-1)(p+1)/2(mod p)
所以模p的所有二次剩余乘积模p的剩余为(-1)(p+1)/2得证。
（2）1，2，3,…p-1为p的一个完全剩余系
1*2*2…*(p-1)≡-1(mod p) ≡(-1)(p+1)/2(-1)(p-1)/2(mod p)
因为模p的所有二次剩余乘积模p的剩余为(-1)(p+1)/2
所以模p的所有非二次剩余乘积模p的剩余为(-1)(p－1)/2
（3）当p=3时，其二次剩余只有1，所以p=3时，模p的所有二次剩余之和模p
的剩余为1
当p>3时，由（1）得a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(mod p)
因为p为奇素数，所以p只能取3k-1或3k+1形式，代入上式得0
所以当p>3时，模p的所有二次剩余之和模p的剩余为0。
（4）因为模p的所有二次非剩余之和与所有二次剩余之和的和可以被p整除
所以由(3)得，当p=3时，模p的所有二次非剩余之和模p的剩余为-1;
当p>3时，模p的所有二次非剩余之和模p的剩余为0。16．解：(1）.因为（7/227）=(-1) (227-1)(7-1)/(2*2)*(227/7)= 1
所以7是227的二次剩余
所以x2≡7(mod227)有解
(3）.因为11对91的逆元是58
所以原同余方程等价于x 2
≡16(mod91)
又16是91的平方剩余
所以11x 2≡-6(mod91)有解
21．证明：应用模重复平方法
11=20+21+23
令x=23,b=2,a=1
(1)x 0=1 a 0=a*b ≡2(mod23) b 1=b 2≡4(mod23)
(2)x 1=1 a 1=a 0*b 1≡8(mod23) b 2=b 12≡16(mod23)
(3)x 2=0 a 2=a 1*b 20≡8(mod23) b 3=b 22≡3(mod23)
(4)x 3=1 a 3=a 2*b 3≡1(mod23)
所以211≡1(mod23) 即23|211-1
47|223-1与503|2251-1 应用同样的方法得证。
第五章．原根与指标
1．解：因为?(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a d
(mod12) 因为21≡2, 22≡4, 23≡8, 24≡3, 26≡-1, 212
≡1(mod13)
所以2模13的指数为12；
同理可得：5模13的指数为4，10模13的指数为6。
2．解：因为?(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a d (mod12)
因为31≡3, 32≡9, 33≡8, 36≡7, 39≡-1, 218≡1(mod13)
所以3模19的指数为18；
同理可得：7模19的指数为3，10模19的指数为18。
3．解：因为?(m)=?(81)=54=2*33,所以?(m)的素因数为q 1=2,q 2=3,进而
?(m)/q 1=27, ?(m)/q 2=18
这样，只需验证：g 27,g 18模m 是否同余于1。对2，4，5，6…逐个验算：
因为227≠1(mod81) 218≠1(mod81) 根据5.2定理8得
所以2是模81的原根
7．证明：因为（a, m ）=1, 故由ord m (a)=st 知：a st ≡1(mod m) 即(a s )t ≡1(mod m)
不妨令ord m (a s )=r 则a sr ≡1(mod m) 所以st|sr
由(a s )t ≡1(mod m)得r|t 即t ＝k*r k ∈N ≥1 r ≤t 所以sr ≤st
所以sr=st 所以r=t
所以ord m (a s )=t
8．解：存在
举例：如n=7,d=3 因为?(7)=6 d=3|6 存在a=2 (2,7)=1, 2
?(7)≡1(mod 7) 又23≡1(mod 7) 所以ord 7(2)=3 满足条件。
10．证明：因为p 为一个奇素数，p-1/2也是一个奇素数
所以?(p)=p-1=2*(p-1)/2 即?(p)的不同素因数为2，p-1/2 又因为a
?(p)/2=a p-1/2≠1(mod p) a ?(p)/[(p-1)/2]=a 2≠1(mod p) 根据5.2定理8得a 是模p 的原根。
15．证明：反证法
假设n是一个合数，令ord n(a)=m 则a m≡1(mod n)
因为a n-1≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m
对n-1的所有素因数q，必可找到一个q1使m|((n-1)/q1)
所以a n-1/q=a m*t≡1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。16．解：因为d=(n,?(m))=(22,?(41))=(22,40)=2 ind5=22
所以(n,?(m))|ind5，同余式有解
等价同余式为22indx≡ind5(mod40) 即11indx≡11(mod20)
解得：indx=1,21(mod40)
所以原同余式解为x=6,35(mod41)
17．解：因为d=(n,?(m))=(22,?(41))=(22,40)=2 ind29=7
(2,7)=1 所以原同余式无解。
第六章．素性检验
1．证明：因为91=13*7是奇合数， (3,91)=1
又36=729≡1(mod91) 则391-1=390≡(36)15≡1(mod91)
则91是对于基3的拟素数。
2．证明：因为45=5*3*3是奇合数， (17,45)=1
由Euler定理：174≡1(mod5) 172≡1(mod3)
所以174≡1(mod3) 所以174≡1(mod45)
则1745-1=1744≡(174)11≡1(mod45)
则45是对于基17的拟素数。
同理45是对于基19的拟素数。
9．证明：25=5*5是奇素数设n=25 n-1=24=23*3 则t=3 (7,25)=1
73≡18(mod25) 72*3≡-1(mod25)
所以25是基于7的强拟素数。
14．证明：n=561=3*11*17 为奇素数（561,2）=1
b(n-1)/2≡2(561-1)/2≡2280≡1(mod561)
(b/n)=(2/561)=(-1)(561*561-1)/8=1
所以2280≡(2/561)(mod561)
所以561是对于基2的Euler拟素数。
信息安全数学基础期末考试试卷及答案(A卷)
信息安全数学基础期末考试试卷及答案（A 卷） 一、 填空题（本大题共8小题，每空2分，共24分） 1. 两个整数a ，b ，其最大公因数和最小公倍数的关系为 ________________。 2. 给定一个正整数m ，两个整数a ,b 叫做模m 同余，如果______________，记作(mod )a b m ≡；否则，叫做模m 不同余，记作_____________。 3. 设m ，n 是互素的两个正整数，则()mn ?=________________。 4. 设1m >是整数，a 是与m 互素的正整数。则使得1(mod )e a m ≡成立的最小正 整数e 叫做a 对模m 的指数，记做__________。如果a 对模m 的指数是()m ?，则a 叫做模m 的____________。 5. 设n 是一个奇合数，设整数b 与n 互素，如果整数n 和b 满足条件 ________________，则n 叫做对于基b 的拟素数。 6. 设,G G '是两个群，f 是G 到G '的一个映射。如果对任意的,a b G ∈，都有 _______________，那么f 叫做G 到G '的一个同态。 7. 加群Z 的每个子群H 都是________群，并且有0H =<>或 H =______________。 8. 我们称交换环R 为一个域，如果R 对于加法构成一个______群，* \{0}R R =对 于乘法构成一个_______群。 二、计算题（本大题共 3小题，每小题8分，共24分） 1. 令1613,a = 3589b =。用广义欧几里德算法求整数,s t ，使得 (,)sa tb a b +=。
信息安全数学基础参考试卷
《信息安全数学基础》参考试卷 一．选择题(在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内，多选不给分)：（每题2分，共20分）1．576的欧拉函数值?(576) ＝()。 (1) 96，(2) 192，(3) 64，(4) 288。 2．整数kn和k(n+2)的最大公因数(kn , k(n+2))=()。 (1) 1或2，(2) | kn|， (3) | n|或| kn|，(4) | k|或2| k|。 3．模10的一个简化剩余系是( )。 (1) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，(2) 11, 17, 19 , 27 (3) 11, 13, 17, 19，(4) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9。 4．29模23的逆元是( )。 (1) 2，(2) 4， (3) 6，(4) 11。 5．设m1，m2是两个正整数，x1遍历模m1的完全剩余系，x2遍历模m2的完全剩余系，若( )遍历m1m2的完全剩余系。 (1) (m1，m2)=1，则m1x1＋m2x2(2) m1和m2是素数，则m1x1＋m2x2 (3) (m1，m2)=1，则m2x1＋m1x2(4)m1和m2是素数，则m2x1＋m1x2 6．下面的集合和运算构成群的是( ) 。 (1)
信息安全数学基础第一阶段知识总结
信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义1 设a 、b 是两个整数，其中b ≠0如果存在一个整数 q 使得等式 a=bq 成立，就称b 整除a 或者a 被b 整除，记作b|a ，并把b 叫作a 的因数，把a 叫作b 的倍数.这时，q 也是a 的因数，我们常常将q 写成a ／b 或 否则，就称b 不能整除a 或者a 不能被b 整除，记作a b. 2整除的基本性质 (1)当b 遍历整数a 的所有因数时，-b 也遍历整数a 的所有因数. (2)当b 遍历整数a 的所有因数时，a/b 也遍历整数a 的所有因数. (3)设b ，c 都是非零整数， (i)若b|a ，则|b|||a|. (ii)若b|a ，则bc|ac. (iii)若b|a ，则1<|b|?|a|. 3整除的相关定理 (1) 设a ，b ≠0，c ≠0是三个整数.若c|b ，b|a ，则c|a. (2) 设a ，b ，c ≠0是三个整数，若c|a ，c|b ，则c|a ±b (3) 设a ，b ，c 是三个整数.若c|a ，c|b 则对任意整数s ，t ，有c|sa+tb. (4) 若整数a 1 , …,a n 都是整数c ≠0的倍数，则对任意n 个整数s 1，…，s n ，整数 是c 的倍数 a b n n a s a s ++ 11
(5) 设a，b都是非零整数.若a|b，b|a，则a=±b (6) 设a, b , c是三个整数，且b≠0，c ≠0，如果(a , c)=1,则 (ab , c)=(b , c) (7) 设a , b , c是三个整数，且c≠0，如果c｜ab , (a , c) = 1, 则c | b. (8) 设p 是素数，若p |ab , 则p |a或p|b (9) 设a1, …,a n是n个整数，p是素数，若p| a1…a n,则p一定整除某一个a k 二整数的表示 主要掌握二进制、十进制、十六进制等的相互转化. 三最大公因数和最小公倍数 (一)最大公因数 1．最大公因数的概念 定义：设是个整数，若使得，则称为的一个因数．公因数中最大的一个称为的最大公因数．记作. 若 ,则称互素． 若,则称两两互素． 思考：1．由两两互素，能否导出 2．由能否导出两两互素？ 2．最大公因数的存在性 (1)若不全为零，则最大公因数存在并且 (2)若全为零，则任何整数都是它的公因数．这时，它们没有最大公因数．
信息安全数学基础试题
一、单项选择题 1、设a, b 都是非零整数。若a |b ，b |a ，则【 】 A.a ＝b B.a ＝± b C.a ＝－b D. a > b 2、设a, b, c 是三个整数，c ≠0且c |a ，c |b ，如果存在整数s, t, 使得sa ＋tb ＝1，则【 】 A.(a, b)= c B. c ＝1 C.c ＝sa ＋tb D. c ＝± 1 3、Fermat 定理：设p 是一个素数，则对任意整数a 有【 】 A. a p ＝1 (mod p) B. a ? (p)＝1 (mod a) C. a ? (p)＝a (mod p) D. a p ＝a (mod p) 4、已知模41的一个原根是6，则下列也是41的原根的是【 】 A. 26 B. 36 C. 46 D. 56 5、已知，),(88+z 是模8的剩余类加群，下述不正确的是【 】 A. [1] 是生成元 B.有3阶子群 C. [0] 是单位元 D.有真子群 6、设
级信息安全数学-12级信息安全数学基础试题
简答题（共20分，每题4分） 1.简述公钥密码学所基于的三个难解数学问题. 2.写出模15的一个简化剩余系，要求每个数都是偶数. 3.一次同余式在什么情况下有解，有多少个解? 4.模m原根存在的充分必要条件是什么? 5.写出3次对称群的所有3阶子群. 判断题（共20分，每题2分，对的打“√”，错的打“×”） 1.质数有无穷多.（） 2.设n是正整数，则.（） 3.有限域的特征一定是质数.（） 4.3是模7的平方剩余.（） 5.根据雅可比符号，可以判断a是模m的平方剩余.（） 6.Klein四元群是最小的非循环群.（） 7.高次同余式解的个数小于或等于它的次数.（） 8.同余式成立.（） 9.的最后两位数字是01.（） 10.整环R中既没有乘法单位元也没有零因子.（） 计算题（50分） 1.计算欧拉函数.（5分） 2.计算勒让德符号.（5分） 3.设,计算.（5分） 4.计算5,10模13的指数.（5分） 5.求解同余式组（10分） 6.构造4元有限域，并给出加法表和乘法表.（10分） 7.设F17上椭圆曲线E:上的点Q=(6,6)，计算2Q，3Q.（10分）证明题（10分，每题5分） 1.设m, n为正整数且m为奇数，证明：2m-1与2n+1互质. 2.证明：是F2[x]中的不可约多项式.
2012级《信息安全数学基础》考试试题(A)参考答案 简答题（共20分，每题4分） 1．公钥密码学所基于的三个难解数学问题是：大因数分解问题；离散对数问题和椭圆曲线离散对数问题； 2. 16,2,4,22, 8, 26, 20, 14(答案不唯一)； 3. 时有解，有个解； 4. ,p 为奇质数； 5. {e, (123),(132)} 二．判断题（共20分，每题2分，对的打“√”，错的打“×”） 1. √； 2. ×； 3. √； 4. ×； 5. √×； 6. √； 7. √； 8. ×； 9. √；10. ×； 三．计算题（50分） 1. 解： 2. 解： 3.解：. 4.解：根据定义计算得 5.解：先求 得：， 即， 即 所以同余式的解为： 6.解：, 加法表： + 1 x x+1 1 x x+1 1 1
信息安全数学基础习题集一
信息安全数学基础----习题集一 一、填空题 1、设a=18、b=12，c=27，求a、b、c的最小公倍数[a,b,c]= . 2、求欧拉函数= . 3、设，则模的最小非负简化剩余系{ }. 4、设，则模的所有平方剩余= . 5、设，则模的所有原根个数= . 6. 设m，n是互素的两个正整数，则φ(mn)=________________。 7. 设m是正整数，a是满足的整数，则一次同余式：ax≡b (mod m)有解的充分必要条件是_________________ 。 8. 设m 是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m ，使得aa’≡1 (mod m)。 9. 设, 如果同余方程__________, 则叫做模的平方剩余. 10. 设, 则使得成立的最小正整数叫做对模 的__________. 二、判断题（在题目后面的括号中，对的画“”，错的画“”） 1、若是任意正整数, 则. （） 2、设是个不全为零的整数，则与, ||, ||,…, ||的公因数相同（） 3、设是正整数, 若, 则或. （） 4、设为正整数, 为整数, , 且, 则. （） 5、{1,-3,8,4,-10}是模5的一个完全剩余系. （） 6、设是素数, 模的最小非负完全剩余系和最小非负简化剩余系中元素个数相等. （） 7、设为奇素数, 模的平方剩余和平方非剩余的数量各为8. （） 8、一次同余方程有解. （） 9、设是素数, 是模的原根, 若, 则是的整数倍. （）
10、设, 则, …, 构成模的简化剩余系. （） 11. , 则＝. （） 12. 设是两个互素正整数, 那么, 则. （） 13. 设m是一个正整数, a,b,d都不为0，若ad≡bd(modm)。则a≡b(mod m)。 （） 14. 设为正整数, a是满足的整数，b为整数. 若为模的一个简 化剩余系, 则也为模的一个简化剩余系. （） 15. p为素数,n为整数且与p互素，则n2为模p的平方剩余. （） 16. 设为正整数, 设, 则是模的平方剩余的充要条件是: . （） 17. 3是模7的原根。（） 18. 设为正整数, 若，则. （） 19. 整数集关于整数的乘法构成群。（） 20. 适当定义加法和乘法，集合{0,1}可以构成一个有限域。（） 三、单项选择题（把答案写在题目后面的括号中） 1. 设与是两个整数, 则存在整数, 使得，下面关于与线性组合描述错误的是：（） A. 整数的取值仅有一组唯一的值； B. 整数的线性和所能表示的最小的正整数是最大公因数，即； C. 的倍数也可以用的线性和表示； D. 整数，可以使用辗转相除法(欧几里得算法)反推得到。 2、下面关于整除的描述错误的是：（） A. ±1是任何整数的因子； B.设（整数集合）,, , 则； C. 0是任何整数的倍数； D. 设, 若, ，则, 。
信息安全数学基础(A)答案
贵州大学2007-2008学年第二学期考试试卷（标准答案） A 信息安全数学基础 注意事项： 1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。 2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。 3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。 4. 满分100分，考试时间为120分钟。 一、设a,b 是任意两个不全为零的整数，证明：若m 是任一整数，则 [am,bm]=[a,b]m.(共10分) 解： 2 2[,](3(,)(3(,)(2( ,) [,](2abm am bm am bm abm a b m abm a b a b m = == =分） 分） 分） 分） = = 二、设 n=pq,其中p,q 是素数.证明：如果 2 2 =(mod ),,,a b n n a b n a b -+宎宎 则(,)1,(,)1n a b n a b ->+>（共10分） 证明：由2 2 2 2 =(mod ),|-,|()()a b n n a b n a b a b +-得即a a (2分） 又n pq =，则|()(),|()|(),pq a b a b p p a b p a b +-+-因为是素数，于是或a a a (2分） 同理，|()|()q a b q a b +-或a a (2分） 由于,n a b n a b -+宎 ，所以如果|()p a b +a ，则|()q a b -a ，反之亦然. (2分） 由|()p a b +a 得(,)1n a b p +=> (1分） 由|()q a b -a 得(,)1n a b q -=> (1分）
信息安全数学基础第一阶段知识总结
信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义1 设a 、b 是两个整数，其中b ≠0如果存在一个整数 q 使得等式 a=bq 成立，就称b 整除a 或者a 被b 整除，记作b|a ，并把b 叫作a 的因数，把a 叫作b 的倍数.这时，q 也是a 的因数， 我们常常将q 写成a ／b 或 否则，就称b 不能整除a 或者a 不能被b 整除，记作a b. 2整除的基本性质 (1)当b 遍历整数a 的所有因数时，-b 也遍历整数a 的所有因数. (2)当b 遍历整数a 的所有因数时，a/b 也遍历整数a 的所有因数. (3)设b ，c 都是非零整数， (i)若b|a ，则|b|||a|. (ii)若b|a ，则bc|ac. (iii)若b|a ，则1<|b|≤|a|. 3整除的相关定理 (1) 设a ，b ≠0，c ≠0是三个整数.若c|b ，b|a ，则c|a. (2) 设a ，b ，c ≠0是三个整数，若c|a ，c|b ，则c|a ±b (3) 设a ，b ，c 是三个整数.若c|a ，c|b 则对任意整数s ，t ， a b
有c|sa+tb. (4) 若整数a 1 , …,a n 都是整数c ≠0的倍数，则对任意n 个整数s 1，…，s n ，整数 是c 的倍数 (5) 设a ，b 都是非零整数.若a|b ，b|a ，则a=±b (6) 设a, b , c 是三个整数，且b ≠0，c ≠0，如果(a , c)=1,则 (ab , c)=(b , c) (7) 设a , b , c 是三个整数，且c ≠0，如果c ｜ab , (a , c) = 1, 则c | b. (8) 设p 是素数，若p |ab , 则p |a 或p|b (9) 设a 1 , …,a n 是n 个整数，p 是素数，若p| a 1 …a n ,则p 一定整除某一个a k 二 整数的表示 主要掌握二进制、十进制、十六进制等的相互转化. 三 最大公因数和最小公倍数 (一)最大公因数 1．最大公因数的概念 定义：设是 个整数，若 使得 ， 则称 为 的一个因数．公因数中最大的一个称为 的最大公因数．记作 . 若 ,则称 互素． 若 ,则称 两两互素． n n a s a s ++ 11
信息安全数学基础课后答案完整版Word版
第一章参考答案 （1） 5,4,1,5. （2） 100=22*52, 3288=23*3*137. （4） a,b可以表示成多个素因子的乘积a=p 1p 2 ––p r , b=q 1 q 2 ––q s ,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子 相乘a n=(p 1p 2 ––p r )n, b n=(q 1 q 2 ––q s )n明显a n, b n也没有公共(相同)素因子. （5）同样将a, b可以表示成多个素因子的乘积a=p 1p 2 ––p r , b=q 1 q 2 ––q s , a n=(p 1p 2 ––p r )n, b n=(q 1 q 2 ––q s )n,因为a n| b n所以对任意的i有, p i 的n次方| b n, 所以b n中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b. （6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p 1p 2 ––p r , b=q 1q 2 ––q s , ab=p 1 p 2 ––p r q 1 q 2 ––q s , 又因为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=k 1m+r, bc=k 2 m+r,有 ac=k 1d(m/d)+r, bc=k 2 d(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)都不能 第二章答案 （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)
信息安全数学基础习题答案
信息安全数学基础习题答案 第一章整数的可除性 1．证明：因为2|n 所以n=2k , k∈Z 5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z 7|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|n 2．证明：因为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为素数。 由737=11*67 ,747=3*249 知737与747都为合数。 8．解：存在。eg：a=6,b=2,c=9 10．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈N+ 又p1≤p2≤p3，所以n= p1 p2 p3k≥p13 即p13≤n1/3 p1为素数则p1≥2，又p1≤p2≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p22 即p2≤(n/2)1/2得证。 11．解：小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数： 12．证明：反证法 假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相 乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个3k+1的素数相乘，得
信息安全数学基础期末考试试卷及答案(A卷)
信息安全数学基础期末考试试卷及答案(A卷) 一、填空题(本大题共8小题，每空2分，共24分) 1.两个整数a，b，其最大公因数和最小公倍数的关系为 。 2.给定一个正整数m，两个整数a,b叫做模m同余，如果 ____________________________ ，记 作a三b(modm)；否则，叫做模m不同余，记作 ________________________ 。 3.设m，n是互素的两个正整数，则 ?(m n)= ______________________________ 。 e .. 4.设m 1是整数，a是与m互素的正整数。则使得a三1(modm)成立的最小正 整数e叫做a对模m的指数，记做 ________________ 如果a对模m的指数是? (m)，贝U a叫做模m的________________ 。 5.设n是一个奇合数，设整数b与n互素，如果整数n和b满足条件 ______________________ ，贝U n叫做对于基b的拟素数。 6.设G,G是两个群，f是G到G的一个映射。如果对任意的a,b G，都有 __________________ ，那么f叫做G到G'的一个同态。 7.加群Z的每个子群H都是 _______________________________ 群，并且有H M O A或 H = _____________________ 。 8.我们称交换环R为一个域，如果R对于加法构成一个 ____________ ，戌=R\{0}对 于乘法构成一个 ____________ 。 二、计算题(本大题共3小题，每小题8分，共24分) 1.令a =1613, b =3589。用广义欧几里德算法求整数s,t，使得sa tb 二(a,b)。
信息安全数学基础知识点
第六章 素性检验 6.1 拟素数 引例：根据Fermat 小定理，我们知道：如果n 是一个素数，则对任 意整数b,(b,n)=1,有 )(mod 11n b n ≡- 由此，我们得到：如果一个整数b,(b,n)=1,使得 ) (mod 11n b n ≡/-，则n 是一个合数。 定义1：设n 是一个奇合数，如果整数b,(b,n)=1使得同余式 )(mod 11n b n ≡-成立，则n 叫做对于基b 的拟素数。 引理：设d,n 都是正整数，如果d 能整除n 则 12-d 能整除12-n 定理1：存在无穷多个对于基2的拟素数。 定理2：设n 是一个奇合数，则 (i)n 是对于基b,((b,n)=1),的拟素数当且仅当b 模n 的指数整除n-1。 (ii)如果n 是对于基1b ((1b ,n)=1),和基2b ，((2b ,n)=1),的拟素数，则 n 是对于基21b b 的拟素数。 (iii)如果n 是对于基b,((b,n)=1),的拟素数，则n 是对于基1-b 的拟素数。 (iv)如果有一个整数b ，((b,n)=1),使得同余式 )(mod 11n b n ≡-不成立，则模n 的简化剩余系中至少有一半的数使得该同余式不成立。 //////////////////////////////////////////////////////////////////////////////////////////////////////////
Fermat 素性检验 给定奇整数3≥n 和安全参数t 。 1.随即选取整数 b ,22-≤≤n b ； 2.计算()n b r n mod 1-=; 3.如果1≠r ，则n 是合数； 4.上述过程重复t 次； 定义2：合数n 称为Carmichael 数，如果对所有的正整数b ，(b,n)=1, 都有同余式 ()n b n mod 11≡-成立 定理3：设n 是一个奇合数。 (i)如果n 被一个大于1平方数整除，则n 不是Carmichael 数。 (ii)如果k p p n Λ1=是一个无平方数，则n 是Carmichael 数的充要条件是 11--n p i ，k i ≤≤1 定理4：每个Carmichael 数是至少三个不同素数的乘积 注：1.存在无穷多个Carmichael 数 2.当n 充分大时，区间[]n ,2内的Carmichael 数的个数大于等于72n 6.2 Euler 拟素数 引例：设n 是奇素数，根据定理，我们有同余式 )(mod 21n n b b n ?? ? ??≡- 对任意整数b 成立 因此，如果存在整数b ，(b,n)=1,使得
信息安全数学基础答案第一二三四五六七八章2
第一章 （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=p1p2––p r, b=q1q2––q s, a n=(p1p2––p r)n, b n=(q1q2––q s)n,因为a n| b n所以对任意的i有, p i的n次方| b n, 所以b n中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b. （6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2––p r, b=q1q2––q s, ab=p1p2––p r q1q2––q s, 又因为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,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!)/(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=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)都不能 第二章 （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
信息安全数学基础考试题
信息安全数学基础2005年考题 1、已知a=66,b=75，求正整数x,y，使ax-by=(a,b)成立 . 2、证明：对于任意整数a、b、c，如果(a,c)=1，c|ab，则必有c|b . 3、集合{0，1，······9998}中有多少个元素与9999互素？ 4、已知a=5,b=42,n=265, 求a b mod n . 5、求如下同余式组的解 x≡1(mod 5) x≡3(mod 7) x≡2(mod 9) 6、求同余式x5-x4+x2+6≡(mod 73)的所有解。 7、求J(29,97)的值。 8、求x2≡13（mod 113）的解。 9、已知59582=2×313，求模59582的一个原根。
1.2008-05-04课堂补充 求F2[x]中f(x)=x8+x4+x3+x+1的周期，并求y∈F2[x]/(f(x))，使得y、y2、y4、y8为F2[x]/(f(x))的基底 2.2008-05-04课堂补充 求F2[x]中f(x)=x8+x4+x3+x2+1的周期，并求y∈F2[x]/(f(x))，使得y、y2、y4、y8为F2[x]/(f(x))的基底 3.2008-05-04课堂补充 设a(x)=x3+x+1，b(x)=x2+x+1，计算a(x)+b(x)、a(x)．b(x)、a(x)/b(x) 4.第11章课件2 证明：如果α≠0和β都是有理数域Q上的代数数，则α+β和α-1也是有理数域Q上的代数数 5.第11章课件3 α叫做代数整数，如果存在一个首一正系数多项式f(x)，使得f(α)=0。证明：如果α≠0和β是代数整数，则α+β和α-1也是代数整数 6.第12章课件3 证明x8+x4+x3+x+1是F2[x]中的不可约多项式，从而F2[x]/(x8+x4+x3+x+1)是一个F28域 7.第12章课件4 求F28=F2[x]/(x8+x4+x3+x+1)中的生成元g(x)，并计算g(x)t，t=1,2,…,255和所有生成元 8.第12章课件3 证明x8+x4+x3+x2+1是F2[x]中的不可约多项式，从而F2[x]/(x8+x4+x3+x2+1)是一个F28域 2008-05-04交，共3题 1.2008-04-18课堂补充 求F2上的所有8次不可约多项式 注：x8+x4+x3+x+1是不可约非本原多项式，用于AES；x8+x4+x3+x2+1是不可约本原多项式，用于欧洲通信标准 提示：非零多项式有28-1=255个，次数为偶数时一定可约，奇数次系数为0时可约 2.2008-04-30课堂补充 求Q(√2，3√3)的基底 3.2008-04-30课堂补充 求u使Q(√2，√3)=Q(u)
信息安全数学基础课后答案完整版.doc
第一章参考答案 (1)5,4,1,5. (2)100=22*52,3288=23*3*137. (4)a,b可以表示成多个素因子的乘积a=pip2—p r? b=q】q2—q、,又因为(a, b)=l, 表明a, b没有公共(相同)素因子.同样可以将a) 9表示为多个素因子相乘a n=(pip2一py, b n=(qiq2一q s)n明显a n, b n也没有公共(相同)素因子. (5 ) 同样将a, b可以表示成多个素因子的乘积a=pip2一p r, b=qiq2—q s, a n=(PiP2—Pr)L b'-(qiq2—s)L因为a n| b“所以对任意的i有,pi的n次方| b n,所以中必然含有a 的所有素因子，所以b中必然含有a的所有素因子，所以a|b. (6)因为非零a, b, c 互素，所以(a, b)=(a, c)=l,又因为a=pip2一Pr, b=qiq2— ab=p)p2—Prqiq?― s,又因为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,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!)/(61!)= 62*63*—*70=(?9)*(?8)*—*(-l)=?9!=?362880=l(mod 71).明显61!与71互素，所以两边同乘以61!,所以70!=61!(mod71). (13)当n为奇数时2n=(.l)n=.l=2(mod 3),两边同时加上1有2n+l=0(mod 3), 所以结论成立. 当n为偶数时2n=(-l)n=l(mod 3),两边同时加上1有2n+l=2(mod 3),所以结论成立. (14 ) 第一个问：因为(c,m)=d, m/d 为整数.假设ac=k]m+r, bc=k2m+r,有ac=k|d(m/d)+r, bc=k2d(m/d)+r 所以ac=bc(mod m/d),因为(c,m/d)=l,所以两边可以同除以一个c,所以结论成立. 第二个问题：因为a=b(mod m),所以a.b=ki*m“ a-b是任意mi的倍数，所以a.b是mi公倍数，所以[mj]|a.b.(利用式子：最小公倍数=每个数的乘积/最大公约数，是错误的，该式子在两个数时才成立) (15) 将整数每位数的值相加，和能被3整除则整数能被3整除，和能被9整除则整数能被9整除,(1)能被3整除，不能被9整除，(2)都不能，(3)都不能，(4) 都不能 第二章答案 (5)证明：显然在群中单位元c满足方程x2=x,假设存在一?个元素a满足方程x2=x，则有a2=a，两边同乘以广有3『.所以在群中只有单位元满足方程x2=x. (6)证明：因为群G中每个元素都满足方程x2=e,所以对群中任意元素a,b 有aa=e, bb=e, (ab)?=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-l ababb_,= a_,aabbb-1,有ab=ba,所以G是交换群.
信息安全数学基础参考试卷
,考试作弊将带来严重后果！ 华南理工大学期末考试 XXXX 级《信息安全数学基础》试卷A 1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3．考试形式：闭卷；不许使用计算器； 选择题(在每小题的备选答案中只有一个正确答案，将正确答案序号填入下)： （每题2分，共10分） 1．设 m 是大于 1 的整数, a 是满足(a , m )＝1 的整数,则 ( )。 (1) a m ≡a (mod ? (m ))， (2) a ? (m )≡a (mod m )， (3) a m ≡1 (mod ? (m ))， (4) a ? (m )≡1 (mod m )。 2．设m 是一个正整数，a , b 是整数，下面正确的是( )。 (1) 若ad ≡bd (mod m )，则 a ≡b (mod m )； (2) 若a ≡b (mod m ) , 则 ak ≡bk (mod mk )； (3) 若a ≡ b (mod m )，正整数 d | (a , b , m )，则 mod()a b m d d d ≡； (4) a ≡b (mod m )， 如果m | d ，则 a ≡b (mod d )。 3．整数kn 和k (n +2)的最大公因数(kn , k (n +2))=( )。 (1) 1或2， (2) | kn |， (3) | n | 或 | kn |， (4) | k | 或2| k | 。 4．设 a ＝23×32×54×116 ，b ＝22×36×74×113，使得a' | a ，b' | b ，a' ×b'＝[a ，b ]，a'，b' )＝1 的a'，b' 分别为( )。 (1) 54 ×116 ，22×36×74， (2) 23×54 ，36×74×113， (3) 23×54 ×116 ，36×74， (4) 23×54 ×116 ，36×74×113 5．集合F 上定义了“＋”和“ · ”两种运算。如果( )，则
2012年信息安全数学基础期末考试试题
2012年信息安全数学基础期末考试试题 1证明：如果是整数，则能被3整除。 2 用广义欧几里德算法求最大公因子 3 设是一个正整数，，如果，证明：。 4 解方程 5 解方程组 6 计算3模19的指数。
7、计算的Legendre符号 2012年信息安全数学基础期末考试试题 答案 1 证明：因为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整除。 2. 12075=2*4655+2765 4655=1*2765+1890 2765=1*1890+875 1890=2*875+140 875=6*140+35 140=4*35 所以=35
3. 因为d|m，所以存在整数使得。又因为，所以存在整数使得。该式又可以写成。故。 4. 计算最大公因式(987,2668)=1，所以原同余式有解且只有一个解。利用广义欧几里德除法，求同余式的解为。再写出同余式的解为。 5 令，， 。 分别求解同余式（i=1,2,3） 得到，，。故同余式的解为 6 解：因为(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a d(mod12) 因为31≡3, 32≡9, 33≡8, 36≡7, 39≡-1, 218≡1(mod13) 所以3模19的指数为18； 7 8 证明：因为91=13*7是奇合数， (3,91)=1 又36=729≡1(mod91) 则391-1=390≡(36)15≡1(mod91) 则91是对于基3的拟素数。 9 对任意，有，从而， 。
- 信息安全数学基础(A)答案
- 信息安全数学基础习题集一
- 信息安全数学基础习题第三章答案.doc
- 信息安全数学基础期末试卷
- 信息安全数学基础课件
- 信息安全数学基础课后答案完整版Word版
- 信息安全数学基础课后答案完整版.doc
- 信息安全数学基础知识点
- 信息安全数学基础教学大纲
- 信息安全数学基础作业参考答案
- 信息安全数学基础
- 信息安全数学基础习题集一
- 《信息安全数学基础》课程教学大纲
- (完整)信息安全数学基础期末试卷及答案,推荐文档
- 信息安全数学基础参考试卷
- 信息安全数学基础第一阶段知识总结
- 信息安全数学基础课后答案陈恭亮著清华大学出版社
- 信息安全数学基础试题
- 信息安全数学基础知识点
- 信息安全数学基础-知识点总结