现代密码学第4章习题.pdf

《现代密码学第4章习题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章习题1．证明以下关系(1)(amodn)=(bmodn)，则a≡bmodn；(2)a≡bmodn，则b≡amodn；(3)a≡bmodn，b≡cmodn，则a≡cmodn。证明：（1）设(amodn)=r，(bmodn)=r，则存在整数j、k使得a=jn+r，b=kn+r。因此a−b=(j−k)n，则n

2、a−b，所以a≡bmodn。（2）因为a≡bmodn，所以，m

3、a−b，⇒m

4、b−a⇒b≡amodn。（3）由a≡bmodn，b≡cmodn，得n

5、a−b，n

6、b−c，⇒n

7、(a−b)+(b−c)=a−c，所以a≡cmodn。2．证明以

8、下关系(1)[(amodn)−(bmodn)]modn=(a−b)modn；(2)[(amodn)×(bmodn)]modn=(a×b)modn。证明：（1）设(amodn)=r，(bmodn)=r，则存在j、k使得a=jn+r，b=kn+r。abab则(a−b)modn=[(j−k)n+r−r]modn=(r−r)modnabab=[(amodn)−(bmodn)]modn（2）设(amodn)=r，(bmodn)=r，则存在j、k使得a=jn+r，b=kn+r。abab则(a×b)modn=[(jkn+jr+kr)n+rr]modn=(r

9、r)modnbaabab=[(amodn)×(bmodn)]modn2013．用Fermat定理求3mod11。10解：因11是素数，且gcd(3，11)＝1，则有Fermat定理得3≡1mod11，又根据性质[(amodn)×(bmodn)]modn=(a×b)modn，2002012001得3≡1mod11，3mod11=[(3mod11)×(3mod11)]mod11=3mod11。4．用推广的Euclid算法求67mod119的逆元。解：用用推广的Euclid算法求67mod119的逆元运算步骤如下：循环次数QX1X2X3Y1Y2Y3

10、初值－1011901671101671-152211-152-121533-12154-77424-77-9161−1所以67mod119=16。5．求gcd(4655,12075)。解：12075=2×4655+27654655=1×2765+18902765=1×1890+8751890=2×875+140875=6×140+35140=4×35+0所以gcd(4655,12075)=35。6．求解下列同余方程组：x≡2mod3x≡1mod5x≡1mod7解：M=3×5×7=105，M=35，M=21，M=15，易求123−1−

11、1−1e≡Mmod3≡2,e≡Mmod5≡1,e≡Mmod7≡1,112233所以xmod105≡(35×2×2+21×1×1+15×1×1)mod105≡71。即x≡71mod105。7．计算下列Legendre符号：2665(1)；(2)；(3)。5953107解：259−12(1)=(−1)8=−1；59262353－13532+17×32()2＝＝()－18＝(－1)=(−1)=(−1)5353535333

12、323−1=(−1)(−1)8=1265−165107426723737(3)=====(−1)8107656565656565656565223−17−165652+21×32+9×722====(−1)8(−1)8=−13737378．求25的所有本原根。12解：ϕ(25)=25(1−)=20=2⋅5，ϕ(25)的所有不同素因子q＝2，q=5，所以

13、对每12510411个g，只需计算g和g。又因ϕ(24)=24(1−)(1−)=8，所以25有8个本原根。231041041=1mod25，1=1mod25；2=24mod25，2=16mod25；1041043=24mod25，3=6mod25；4=1mod25，4=6mod25；1001045=0mod25，5=0mod25；6=1mod25，6=21mod25；1041047=24mod25，7=1mod25；8=24mod25，8=21mod25；1041049=1mod25，9=11mod25；10=0mod25，10=0mod25

14、；10410411=1mod25，11=16mod25；12=24mod25，12=11mod25；10410413=24mod25，13=11mod25；14=1