信息安全数学基础习题集一

信息安全数学基础----习题集一

一、填空题

1、设a=18、b=12，c=27，求a、b、c的最小公倍数[a,b,c]=.

2、求欧拉函数φ(3000)=.

3、设m=9，则模m的最小非负简化剩余系={}.

4、设m=11，则模m的所有平方剩余=.

5、设m=22，则模m的所有原根个数=.

6.设m，n是互素的两个正整数，则φ(mn)=________________。

7.设m是正整数，a是满足mm的整数，则一次同余式：ax≡b(modm)有解的充分必要条件是_________________。

8.设m是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m，使得aa’≡1(modm)。

9.设m∈m,(m,m)=1,如果同余方程m2≡m(mod m)__________,则m叫做模m 的平方剩余.

10.设m,m∈m,m>1,(m,m)=1,则使得m m≡1(mod m)成立的最小正整数m叫做m对模m的__________.

二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）

1、若m是任意正整数,则(mm,mm)=(m,m). （）

2、设m1,m2,…,m m是m个不全为零的整数，则m1,m2,…,m m与m1,|m2|,|m3|,…,|m m|的公因数相同（）

3、设m是正整数,若m│mm,则m│m或m│m.（）

4、设m为正整数,m,m为整数,m≡m(mod m),m│m且m>0,则m

m ≡m

m

(mod m

m

).

（）

5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）

6、设m是素数,模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等.（）

7、设m=17为奇素数,模m的平方剩余和平方非剩余的数量各为8. （）

8、一次同余方程9m≡1(mod24)有解. （）

9、设m是素数,m是模m的原根,若m m≡1(mod m),则m是m?1的整数倍.（）

10、设m>1,(m,m)=1,则1=m0,m,m2,…,m ord m(m)?1构成模m的简化剩余系.

（）

11.m≠0,则(0,m)＝|m|.（）

12.设m,m是两个互素正整数,那么m│m,m│m,则mm│m.（）

13.设m是一个正整数,a,b,d都不为0，若ad≡bd(modm)。则a≡b(modm)。

（）

14.设m为正整数,a是满足(m,m)=1的整数，b为整数.若m1,m2,…,m m(m)为模m 的一个简化剩余系,则mm1+b,mm2+b,…,mm m(m)+b也为模m的一个简化剩余系.（）

15.p为素数,n为整数且与p互素，则n2为模p的平方剩余.（）

16.设m为正整数,设m∈m,(m,m)=1,则m是模m的平方剩余的充要条件

是:m m+1

2≡1(mod m).（）

17.3是模7的原根。（）

18.设m,m∈m,m>1,(m,m)=1,m为正整数,若m m≡1(mod m)，则ord m(m)|m.（）

19.整数集关于整数的乘法构成群。（）

20.适当定义加法和乘法，集合{0,1}可以构成一个有限域。（）

三、单项选择题（把答案写在题目后面的括号中）

1.设m与m是两个整数,则存在整数m,m,使得(m,m)=mm+mm，下面关于m与m线性组合描述错误的是：（）

A.整数m,m的取值仅有一组唯一的值；

B.整数m,m的线性和所能表示的最小的正整数是m,m最大公因数，即mm+mm= (m,m)；

C.(m,m)的倍数也可以用m,m的线性和表示；

D.整数m,m，可以使用辗转相除法(欧几里得算法)反推得到。

2、下面关于整除的描述错误的是：（）

A.±1是任何整数的因子；

B.设m,m∈m（整数集合）,c≠0m|m,m|m,则m|m±m；

C.0是任何整数的倍数；

D.设m,m∈m,若m|m,m≠0，则m|?m,?m|?m。

3、下面的说法正确的是：（）

A.给定一个正整数m和两个整数m,m，若m≡m(mod m)，则(m?m)|m

B.设m,m为整数,若m≡m(mod m m),(m=1,2,…,m)，则m≡m(mod[m1,m2,…,m m])；

C.设m1,m2是两个正整数,若m1,m2分别遍历m1,m2的完全剩余系,则m2m1+ m1m2遍历模m1m2的完全剩余系；

D.设m为素数,m为任意正整数,则m m?1≡1(mod m)。

4.下面哪个集合是模12的简化剩余系？()。

A.1,3,5,7

B.1,5,7,9,

C.1,5,7,11

D.3,5,7,11。

5.一次同余方程31000m≡9(mod27)的解数是（）

A.3

B.2

C.1

D.0

6、下面的说法正确的是：（）

A.一次同余方程21x≡55(mod77)有解；

B、一次同余方程m≡6(mod15)，等价于求解一次同余方程组:

{m≡2(mod3)

m≡3(mod5)

的解；

C、一次同余方程组{

m≡5 (mod13)

m≡20 (mod23)

有且仅有唯一的解；

D.设m m,m m是正整数,对于一次同余方程组m≡m m(mod m m),m=1,2,3,若

(m m,m m)=1,则同余方程组一定有解。

7、设m是奇素数,(m1,m)=1,(m2,m)=1,则下列说法错误的是:（）

A.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方剩余.

B.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方非剩余.

C.如果m1,m2都是模m的平方剩余,则m1m2是模m的平方剩余.

D.如果m1,m2都是模m的平方非剩余,则m1m2是模m的平方剩余.

8、下面说法，错误的是（）

A、设p为奇素数，设m∈m,(m,m)=1,若m m?1

2≡?1(mod m)，方程m2≡m(mod m)

方程肯定无解；

B、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余，则m不是模mm的平方剩余；

C、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余,m既不是模m的平方剩余也不是模m的平方剩余，则mm不是模m的平方剩余；

D、设m,m是奇素数,（mm,mm）=1,只有m2≡mm(mod m))和m2≡mm(mod m)同时有解，对于二次方程m2≡mm(mod mm)才有解。

9、已知5对模17的阶为16,5×5≡8(mod17),求ord17(8)的值是（）

A、2

B、4

C、6

D、8

10、下面说法错误的是（）

A、设m是一个正合数,m m={0,1,2,3,…,m?1},则集合m m\{0}对于乘法:

mm=m×m(mod m)

构成一个交换群；

B、设m是一个正整数,令m={…,?m,…,?2,?1,0,1,2,…,m,…},即m是所有整数的集合.对于通常意义的加法(+)，m是一个交换群；

C、设m是一个素数,m m=m/mm={0,1,2,3,…,m?1},m?=m m\{0},m?是模m的最小非负简化剩余系.则集合m?对于乘法:

mm=m×m(mod m)

构成一个交换群；

D、设m是一个奇素数,m m={0,1,2,3,…,m?1},则集合m m\{0}对于乘法:

mm=m×m(mod m)

构成一个有限域。

11．设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

12.设a,b,c是三个不全为零的整数。如果a=bq+c,其中q是整数，则有()。

A.(a,b)=(q,c)

B.(a,b)=(b,c)

C.(a,b)=c

D.(a,b)=(a,c)

13.下面哪个集合不是模5的一个完全剩余系？()。

A.1,3,5,7,9

B.2,4,6,8,10

C.0,1,2,11,13

D.0,1,2,13,19。

14.下面哪个集合是模18的简化剩余系？()。

A.-1,5,7,11,13,17

B.-1,5,9,11,13,15,17

C.-5,1,5,7,11,17

D.1,3,5,7,9.11,13,17。

15.满足56≡18(modm)的正整数m(m>2)的个数是()。

A.1

B.2

C.4

D.5

16.30模23的逆元是()。

A.23

B.19

C.10

D.4

17.下列一次同余式无解的是()。

A.12x≡3（mod16）

B.8x≡9（mod19），

C.78x≡30（mod98）

D.111x≡6（mod51）。

18.下面哪个是模13的平方剩余()。

A.5

B.10

C.11

D.7

19．下面各组数中，均为模14的原根的是()。

A.2,3,4,5

B.3,6,8,10

C.9,11,13

D.3,5

20.定义运算：mm=m×m(mod12),下面哪个集合构成一个群.（）

A.{1,2,3,4}

B.{1,3,5,7}

C.{1,,5,7,9}

D.{1,5,7,11}

四、简答题

1.设m=15,m=101,求整数m,m,使得mm+mm=(m,m).（给出具体求解过程）

2.设m,m∈m,m>1,(m,m)=1,m为正整数,则m m≡1(mod m)的充分必要条件

是ord m(m)|m.给出充分性的证明.

3.计算71005(mod15)。（给出具体求解过程，提示：可用欧拉定理或也可中国剩余定理进行求解）

4.求7模26的阶ord

26(7)，并给出所有模26的阶为ord

26

(7)的整数g（1

出具体求解过程）

5.判断同余方程x2≡3(mod11)的解的情况。（给出具体求解过程）

6.设m是一个正合数,m m={0,1,2,3,…,m?1},令m m?=(m/mm)?={m|m∈m m,(m,m)=1},也即模m的最小非负简化剩余系.则集合m m?对于乘法:

mm=m×m(mmmm)

是否构成一个交换群？（请给出详细求解判断过程）

7.a＝42，b＝164，求a和b的最大公因子（a，b）及整数x和y，使

（a,b）＝ax＋by.

8.证明：设m为正整数,m,m为整数,mm≡mm(mod m).若(m,m)=1,则m≡m(mod m).

9.结合欧拉定理和模重复平方算法(或者平方乘算法)计算62025（mod41）

10.写出模17的所有平方剩余。

11.计算5模19的指数ord

19

(5)。

12.设不可约多项式m(m)=m2+m+1，集合G={m0≡1,m1≡m,m2≡m+1}.若定义乘法:mm=m×m(mmmm(m))，根据群的定义，判断{G,}是否构成一个群。

五、综合题（备注，每题必须给出具体求解过程）

1.解一次同余方程175x≡41081×7(mod133).

2.由GF(2)上的4次不可约多项式m(m)=m4+m3+1构成有限域mm(24)，GF(24)中16个域元素，0除外，其余元素可用m的幂次方来表示:

m0≡1,m1≡m,m2≡m2,m3≡m3

m4≡（）m5≡m3+m+1,m6≡（）,m7≡m2+m+1,

m8≡m3+m2+m,m9≡（）,m10≡m3+m,m11≡m3+m2+1, m12≡m+1, m13≡m2+m,m14≡m3+m2 ,m15≡（）

（1）完成上面的填空（4分）。

m4≡.

m6≡

m9≡

m15≡

(2)已知m(m)=m2+1,m(x)=m3+m2+1是GF(24)中的多项式并根据上面的

结果计算

（1）求m(m)⊕m(m)

（2）求m(m)m(m)

（3）求m(m)?1(mod m(m))

（4）求m(m)?1(mod m(m))

3、求解一次同余方程84x+1≡64(mod371).

信息安全数学基础----习题集一答案

第一题填空

1、108

2、800

3、{1,2,4,5,7,8}

4、{1,3,4,5,9}

5、4

6、φ(m)φ(n)

7、(a,m)|b

8、(a,m)=1

9、有解10、阶

二、判断题

1—5：×√××√6-10：×√×√×

11—15：√√××√16-20：×√√×√

三、单项选择题

1-5：ACBCD6-10：CABDA

11-15：DBCCB16-20：CABDD

四、简答题

1、101=15×6+1115=11+411=4×2+34=3×1+1

因此(a,b)=（101,15）=1

1=4-3=4-(11-4×2)=4×3-11=(15-11)×3-11=15×3?11×4

=15×3?(101?15×6)×4=15×27?101×4

因此s=27，t=-4

备注：s=27t=-4不是唯一答案，只要满足mm+mm=(m,m)都正确

2、证明:充分性.由条件ord m(m)|m，证明m m≡1(mod m)

设ord m(m)|m,则存在整数m,使得m=m·ord m(m),

从而

m m≡m m×ord m(m)≡(m ord m(m))m≡1(mod m).

3、解：71005(mod15)，

已知（7,15）=1，由欧拉定理7m（15）≡1(mod15)，78≡1(mod15)

因此71005≡71005（mod8）≡75(mod15)

72≡4(mod15)74≡1(mod15)75≡7(mod15)

因此71005≡7(mod15)

备注：此计算方法不是唯一，也可以用中国剩余定理化简求解

4、（1）已知26=2×13，φ(26)=12。

（2）72≡23≡?3(mod26)，73≡-21≡5(mod26)76≡25≡?1(mod26)，7是模26的一个原根,ord

26

(7)=12

因为模12的简化剩余系为{1,5,7,11},故模26的所有原根为:

71≡7,75≡11,77≡-33≡-7≡19,711≡-7*9≡-11≡15(mod26).

即模26的原根为:7,11,19,15

5、解：判断同余方程x2≡3(mod11)的解的情况

根据欧拉判别式进行求解进行判断

311?1

2≡35≡12≡1(mod11)

即3是模11的平方剩余，即x2≡3(mod11)方程有解

备注：判断x2≡3(mod11)方程解情况也可采用0,1,…..,5代入方程穷举方法求解。

6、设m是一个正合数,m m={0,1,2,3,…,m?1},令m m?=(m/mm)?={m|m∈m m,(m,m)=1},也即模m的最小非负简化剩余系.则集合m m?对于乘法:

mm=m×m(mmm m)

是否构成一个交换群.

(1)封闭性.对任意m,m∈m m?,恒有mm(mod m)∈m m?.

(2)结合律成立.对任意m,m,m∈m,有(mm)m=m(mm).

(3)恒等元存在,恒等元m=1.即对任意m∈m m?,有m∈m m?,使

mm=mm=m.

(4)对任意m∈m m?,则(m,m)=1，因此存在m的逆元m?1∈m m?,使m m?1=

m?1m=m.

显然,乘法满足交换律,故该群是交换群.

7、164=42×3+3842=38+438=4×9+24=2×2

因此(a,b)=（166,42）=2

2=38-4×9=38-(42-38) ×9=38×10-42×9=(164-42×3)×10-42×9=164×10?42×39备注：不是唯一答案，只要满足mm+mm=(m,m)都正确

8、证明:证明:由mm≡mm(mod m)可得

m│mm?mm=(m?m)m.

而(m,m)=1,故m│(m?m),即m≡m(mod m).

9、解：62017（mod41），

已知（6,41）=1，由欧拉定理6m（41）≡1(mod41)，640≡1(mod41)

因此62017（mod41）≡617（mod41）

62≡?5(mod41)64≡?16(mod41)68≡10(mod41)

616≡18(mod41)

因此62017≡18×6≡26(mod41)

10、1,22≡4(mod17),32≡9(mod17),42≡16(mod17),

52≡8(mod17),62≡2(mod17),72≡15(mod17)，82≡13(mod17)，

模17的所有平方剩余为1，2，4，8，9，13，15，16

11、m(19)=18

52≡6(mod19)，53≡11(mod19)，56≡7(mod19)，59≡1(mod19)(4分)

ord

(5)=9

19

12、(1)封闭性满足

(2)结合律满足

(3)单位元为1

(4)因为1，m，m+1都与m(m)互素，故逆元都存在

{G,}构成一个群。

五、综合题（备注，每题必须给出具体求解过程）

1.解一次同余方程175x≡41081×7(mod133).

解：（1）首先方程可以进行化简（175mod133）x≡42x≡41081×7(mod133)（42,133）=

（6×7,7×19）=7，7|41081×7，因此方程有解，有7个解

（2）φ(133)=6×18=108,4108≡1(mod133)，因此41081(mod133)≡4

因此同余方程175x≡41081×7(mod133)等价于42x≡4×7(mod133)

首先求解6x≡1(mod19)

求解为：x≡-3≡16(mod19)

因此方程的七个解为：x≡-3×4+19t≡-12+19t(mod133)t=0,1,2…,6,即：x≡7,26,,45，64,83,102,121(mod133)

备注：与x≡-3×4+19t≡-12+19t(mod133)t=0,1,2…,6等价都正确。

2.解（1）m4≡m3+1

m6≡m3+m2+m+1

m9≡m2+1

m15≡1

（2）h(x)⊕g(x)=x2+1+x3+x2+1=x3

h(x)g(x)=(x2+1)(x3+x2+1)≡x9×x11≡x3+x+1

h(x)?1(mod f(x))≡（x9）?1

≡x6≡x3+x2+x+1

g(x)?1(mod f(x))≡（x11）?1

≡x4≡x3+1

备注：也可以用多项式直接求解

3、求解一次同余方程84x+1≡64(mod371)

由原方程得84x≡63(mod371)

（84，371）=7|63，故方程有解。

要解84x≡63(mod371)，需先求12x≡9(mod53)的解

先解12x≡1(mod53)

53=12×4+512=5×2+25=2×2+1

1=5-2×2=5-2×（12-5×2）=5×5-12×2

=5×（53-12×4）-12×2=5×53-12×22

故12x≡1(mod53)的解为x≡31（mod53）

12x≡9(mod49)的解为x≡14（mod53）

故84x≡63(mod301)得全部解为x≡14+53t（mod371），4=0,1,2…,6