《信息安全数学基础.doc》由会员分享，可在线阅读，更多相关《信息安全数学基础.doc（13页珍藏版）》请在金锄头文库上搜索。
1、第一章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）=229 求最大公因数（1）（2t-1,2t+1）解：2t+1=（2t-1）*1+2 2
2、t-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
3、 - 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,273553
4、72=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+7t第二章6 2008年5月9日是星期五，问第220080509天是星期几？8 设p是素数，证明：如果a2b2(mod p) 则p|a-b或p|a+b10 设整数a,b,c(c0),满足ab(mo
5、d 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=b24(mod 47)n1=0，a1=a0=1 b2=b1216(mod 47)n2=0，a2=a1=1 b3=b2221(mod 47)n3=0，a3=a2=1 b4=b3218(mod 47)n4=0，a4=a3=1 b5=b4242(mod 47)n5=1，a5=a4*b542(mod 47)2)由费马小定理得2472(mod 47)3)2200=24*47+12(mod 4
6、7)=216(mod 47)=18(mod 47)22 运用wilson定理，求8*9*10*11*12*13（mod 7）24 计算 31000000（mod 7）解：因为361 mod 7 所以31000000=36*166666+4（mod 7）34（mod 7）4（mod 7）35 证明：如果p和q是不同的素数，则pq - 1+qp - 11(mod pq)36 证明：如果m和n是互素的整数，则m(n)+n(m)1(mod mn)第三章1 求求出下列一次同余方程的所有解（1）3x2（mod 7）（2）6x3（mod 9） 解：因为（6,9）=313 所以原同余式有解 同余式6x3（mo
7、d 9）的一个特解x02（mod 9）所以所有解为x2+3t（mod 9） t=0,1,2 即x2,5,8（mod 9）8 求11的倍数，使得该数被2,3,5,7除的余数为1 解：由题意得：x1 mod 2 x1 mod 3 x1 mod 5 x1 mod 7 x=11k M=2*3*5*7=210 M1=3*5*7=105 M1M11mod 2 M1=1 M2=2*5*7=70 M2M21mod 3 M2=1 M3=2*3*7=42 M3M31mod 5 M3=1 M4=2*3*5=30 M4M41mod 7 M4=4 X=105*1*1+70*1*1+42*3*1+3*4*1(mod 21
8、0)1 由得x=2101解非唯一第四章10 计算下列勒让德符号1）（17/37） 2)(151/373) 3)(191/397) 4)(911/2003)16 判断下列同余方程是否有解1） x27（mod 227）25 求所有素数p使得与5为模p的二次剩余 解：由题意得：x25（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的一个本原元，在F
9、101中求log23解：m=10(mod 101)j0123456789yj124816326427547 y=3穷搜：i0123456y*2-pi394501859987所以y*2-10*6 293=269log23=69（二）历年考题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, 求abmod n .5、求如下同余式组的解x1(mod 5)x3(mod 7)x2(mod 9)6、求同余式x5-
10、x4+x2+6(mod 73)的所有解。7、求J(29,97)的值。8、求x213（mod 113）的解。9、已知59582=2313，求模59582的一个原根。1.2008-05-16课堂补充g2(x)=x+1是F28生成元，求g2(x)=x+1的定义多项式h(y)，判断h(y)是否为本原多项式2.2008-05-16课堂补充求出F28的子域及其生成元，以及相应的定义多项式3.2008-05-23课堂补充求F28=F2x/(x8+x4+x3+x2+1)的一个正规基4.2008-05-28课堂补充F17上椭圆曲线E y2=x3+2x+5，求该椭圆曲线的全部点以及阶5.2008-05-28课堂补
11、充F17上椭圆曲线E y2=x3+2x-1，求该椭圆曲线的全部点以及阶 2008-05-16交，共8题1.2008-05-04课堂补充求F2x中f(x)=x8+x4+x3+x+1的周期，并求yF2x/(f(x)，使得y、y2、y4、y8为F2x/(f(x)的基底2.2008-05-04课堂补充求F2x中f(x)=x8+x4+x3+x2+1的周期，并求yF2x/(f(x)，使得y、y2、y4、y8为F2x/(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和都
12、是有理数域Q上的代数数，则+和-1也是有理数域Q上的代数数5.第11章课件3叫做代数整数，如果存在一个首一正系数多项式f(x)，使得f()=0。证明：如果0和是代数整数，则+和-1也是代数整数6.第12章课件3证明x8+x4+x3+x+1是F2x中的不可约多项式，从而F2x/(x8+x4+x3+x+1)是一个F28域7.第12章课件4求F28=F2x/(x8+x4+x3+x+1)中的生成元g(x)，并计算g(x)t，t=1,2,255和所有生成元8.第12章课件3证明x8+x4+x3+x2+1是F2x中的不可约多项式，从而F2x/(x8+x4+x3+x2+1)是一个F28域2008-05-04
13、交，共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，33)的基底3.2008-04-30课堂补充求u使Q(2，3)=Q(u) 2008-04-18交，共9题1.对3DES对称密码算法的S盒进行轮换分解补充：DES算法标准FIPS 46-2 - (DES), Data Encryption Standard页面中搜索“PRIMITIVE FUNCTIONS FOR THE DATA ENCRYPTION ALGORITHM”就可找到标准建议的S盒函数还有一个C语言的3DES实现 FPGA芯片上的3DES实现思路2.第十章课件14证明：置换群S4的一组生成元为(1,2),(1,3),(1,4)进一步，用该组生成元来给出S4的所有子群3.第十章课件154.2008-04-11课堂补充假设K是有限域，p是K的特征。证明：p是奇数，且K的元素个数为pn5.2008-0
