资源描述：
《练习题 信安数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、已知a=66,b=75，求正整数x,y，使ax-by=(a,b)成立 .欧几里德除法75=66+93=66-(75-66)*7=66*8-75*766=9*7+33=66-9*79=3*3所以(66，75)=3x=8，y=72、计算5模11的逆元欧几里德除法、缩系11=5*2+11=11-5*2所以-5*2≡1(mod11)所以模11时，-5和2,5和-2互为逆元3、解方程567x≡21(mod1225)步骤：其实是化简x的系数，第一步：方程最简化，看是否有解第二步：简化以后x系数的逆元，化简x的系数。解：（1）求(56
2、7,1225)1225=567*2+917=(1225-567*2)*25-567*4=1225*25-567*54567=91*6+217=91-(567-91*6)*4=91*25-567*491=21*4+77=91-21*421=7*3所以(567,1225)=7，因为7
3、21，所以有解，有7个解-567*54≡7(mod1225)3、解方程567x≡21(mod1225)-567*54≡7(mod1225)(2)化简方程81x≡3(mod175)-567*54≡7(mod1225)所以-81*54≡1(mod175
4、)所以-81*54*3≡3(mod175)所以x≡-54*3≡-162≡13(mod175)(3)所有解x≡13+175t(mod1225)t=0,1,…,5,64、15的完系和缩系完系：0到14缩系：完系中与模互质的：即与3、5互质1，2，4，7，8，11，13，14全为奇的缩系：1，17，19，7，23，11，13，29剩余类分解：1(mod5)可分解为1,6,11(mod15)5、计算15的欧拉函数ф(15)=ф(3)*ф(5)=2*4=86、化简：115x15+278x3+12(mod12)，x=20系数、指数、底数
5、化简系数：115x15+278x3+12(mod12)≡7x15+2x3+0(mod12)指数：ф(12)=ф(3)*ф(4)=2*2=47x15+2x3(mod12)≡7x3+2x3≡9x3(mod12)底数：9x3(mod12)≡9*203≡9*83≡0(mod12)7、已知a=5,b=42,n=455,求abmodnx≡542(mod455)455=5*7*13x≡542(mod5),x≡542(mod7),x≡542(mod13)x≡0(mod5),x≡50≡1(mod7),x≡56≡-1(mod13)x≡0+1*5
6、*13*(-3)-1*5*7*3≡-300≡155(mod455)13、找出模13的所有原根，有多少个？并据此求出1-12每个数的阶每个元素可能的阶为ф(13)=12的因子从2开始：22≡4，23≡8，24≡3，26≡-1(mod13)，所以2为其中一个原根。原根共ф(12)=ф(4)ф(3)=4个分别为2，25≡6，27≡11，211≡7(mod13)13、找出模13的所有原根，有多少个？并据此求出1-12每个数的阶可能的阶有1，2，3，4，6，12阶1的数有1个：1阶2的数有ф(2)=1个：-1≡12(mod13)阶3的
7、数有ф(3)=2个：24≡3，28≡9(mod13)阶4的数有ф(4)=2个：23≡8，29≡5(mod13)阶6的数有ф(6)=2个：22≡4，210≡10(mod13)阶12的数有4个：2，6，7，1114、1841是强伪素数吗？通过miller-robin素性测试的就是强伪素数1841-1=1840=16*5*232115(mod1841)≡891，8912(mod1841)≡4104102(mod1841)≡5695692(mod1841)≡-255，2552(mod1841)≡590非-1，所以没通过，如果是-1则
8、通过所以1841是合数，不是强伪素数另：安全参数：重复测试的次数16、（Z，*）是群吗？其中*定义为a*b=a+b-4（1）封闭性：a*b=a+b-4，整数运算后仍为整数，所以封闭（2）结合性：(a*b)*c=(a+b-4)*c=a+b-4+c-4=a*(b*c)，所以结合性满足（3）单位元：任意a∈Z，若e为单位元，则a*e=a+e-4=a，所以4为单位元（4）逆元：任意a,b∈Z，a*b=a+b-4=4，则b=8-a，所以逆元为8-a所以，（Z,*）构成群17、（Z12,+12）的各子群子群是与原来的群运算相同，集合为子
9、集合子群具有同样的单位元（Z12,+12）的单位元为0，集合为0-11的整数子群：(1)（Z12,+12）(2)(A1,+12)：A1={0，2，4，8，10}(3)(A2,+12)：A2={0，3，6，9}(4)(A3,+12)：A3={0，4，8}(5)(A4,+12)：A4={0，6
