《密碼學(xué)數(shù)學(xué)基礎(chǔ)》習(xí)題集

北京電子科技學(xué)院《密碼學(xué)數(shù)學(xué)基礎(chǔ)》習(xí)題集信息安全系密碼教研室2015年10月目

錄第一章帶余除法...................................................................................................3一、整數(shù)的最大公因子及其表示..................................................................3二、多項(xiàng)式的最大公因子及其表示..............................................................7三、標(biāo)準(zhǔn)分解和最小公倍數(shù)..........................................................................9四、其他類(lèi)型題............................................................................................11第二章

同余方程...............................................................................................12一、同余性質(zhì)（剩余系）............................................................................12二、模冪運(yùn)算................................................................................................14三、模逆運(yùn)算................................................................................................16四、一次同余方程求解................................................................................18第三章原根計(jì)算.................................................................................................26一、階、原根、指數(shù)....................................................................................26二、階的計(jì)算................................................................................................30三、原根的計(jì)算............................................................................................32四、綜合........................................................................................................36第四章二次剩余.................................................................................................38第五講

群...........................................................................................................49一、群的概念................................................................................................49二、循環(huán)群的生成元求解(可求原根).........................................................49三、子群及其陪集........................................................................................50四、置換群上的計(jì)算....................................................................................53五、群同態(tài)....................................................................................................54第六章

環(huán)的性質(zhì)...............................................................................................55一、環(huán)的概念................................................................................................55二、商環(huán)........................................................................................................57第七章

域上計(jì)算...............................................................................................58第一章帶余除法重點(diǎn)概念：最大公因子、輾轉(zhuǎn)相除法、標(biāo)準(zhǔn)分解式重點(diǎn)內(nèi)容：用輾轉(zhuǎn)相除法求解最大公因子及其表示。一、整數(shù)的最大公因子及其表示1.(288，392)＝

8

，2.設(shè)a=1435,b=3371，計(jì)算(a,b)。答：3371=2?1435+5011435=2?501+433501=433+68433=6?68+2568=2?25+1825=18+718=2?7+47=4+34=3+13=3?1所以(1435,3371)=13.用輾轉(zhuǎn)相除法求整數(shù)x，y，使得1387x-162y=(1387,162)。答：用輾轉(zhuǎn)相除法，如下表計(jì)算：x-yx-yq138710162018911-8171-191202-17311-760199-7712-161374173-625x=73，y=625,(1387,162)=1.4.計(jì)算：(27090,21672,11352)。答：(27090,21672,11352)=(4386,10320,11352)=(4386,1548,2580)=(1290,1548,1032)=(258,516,1032)=(258,0,0)=258。5.用輾轉(zhuǎn)相除法計(jì)算以下數(shù)組的最大公因子。(1)(1046,697)(2)(20301044)解：(1)104616973496971349348349=1?348+1348=348?1因此(1046,697)=1(2)

2030=1?1044+9861044=1?986+58986=17?58因此(20301044)=586.用輾轉(zhuǎn)相除法計(jì)算以下數(shù)組的最大公因子(1)(2104,2720,1046)(2)(27090,21672,11352)解：(1)先求出(2104,2720)的公因子d1，再求(d1,1046)的公因子d2，d2即為最終要求的公因子。因此：2720=1?2104+6162104=3?616+256616=2?256+104256=2?104+48104=2?48+848=6?8因此(2104,2720)=8，再求(8,1046)，1046=130?8+6，，，，8=1?6+26=3?2因此(2104,2720,1046)=2(2)先求出(27090,21672)的公因子d1，再求(d1,11352)的公因子d2，d2即為最終要求的公因子。因此：27090=1?21672+541821672=4?5418因此(27090,21672)=5418，再求(5418,11352)，11352=2?5418+5165418=10?516+258516=2?258因此(27090,21672,11352)=2587.用輾轉(zhuǎn)相除法求以下數(shù)組的最大公因子，并把它表示為這些數(shù)的整系數(shù)線(xiàn)性組合。(1)1387,162(2)2046,1620解：(1)用列表法可求出(1387,162)的公因子及相應(yīng)的系數(shù)組合，如表1所示：表1求(1387,162)的公因子及相應(yīng)系數(shù)u

v

q1387

1

01629171201192

01-12-79-16

1-89-1760-77137

81131141

73

-625

20由上表可得：(1387,162)=1=1387?73+162?(-625)。(2)用列表法可求出(2046,1620)的公因子及相應(yīng)的系數(shù)組合，如表2所示：表2求(2046,1620)的公因子及相應(yīng)的系數(shù)組合u

v

q2046

1

01620426342846

01-34-19

1-14-524

1314140由上表可得：(2046,1620)=6=1387?(-19)+162?24。8.計(jì)算4389，5313，399的最大公因子，并把它表示為這些數(shù)的整系數(shù)線(xiàn)性組合。解：先求4389與5313的最大公因子，如下表3，公因子為213。再求213與399的最大公因子，如表4，公因子為21。表3求4389與5313的最大公因子

表4求213與399的最大公因子u

v

q

u

v

q5313

1

0

399

1

04389924693231

01-45

1-15-6

1413

2311686342

01-13

1-12-5

11210

21

-4

7

20又由表3、4可分別得到如下兩式：231=5313?5+4389?(-6)21=399?(-4)+231?7

(1)(2)將（2）式的231用（1）式等式右邊代替并化解可得如下式：21=399?(-4)+5313?35+4389?(-42)所以得到4389，5313，399的最大公因子為21，及其相應(yīng)系數(shù)組合為-42，35，-4。二、多項(xiàng)式的最大公因子及其表示1、求有理數(shù)域上多項(xiàng)式的最大公因式(f(x),g(x))，其中f(x)=x5+x4+x2+2x+1,g(x)=x4+x3+x2+2x+1.答：用輾轉(zhuǎn)相除法計(jì)算如下x5+x4+x2+2x+1=x(x4+x3+x2+2x+1)-x3-x2+x+1x4+x3+x2+2x+1=-x(-x3-x2+x+1)+(2x2+3x+1)-x3-x2+x+1=

12

x(2x2+3x+1)+

3x344843x33344因此(f(x),g(x))=x+12、求有理數(shù)域上多項(xiàng)式的最大公因式(f(x),g(x))，并計(jì)算u(x),v(x)，使得(f(x),g(x))=u(x)f(x)+v(x)g(x)，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+x-1.答：由列表法可求出(f(x),g(x))的公因子及相應(yīng)系數(shù)組合，如表5所示：表5求(f(x),g(x))的公因子及相應(yīng)的系數(shù)組合u(x)

v(x)

q+2x2+3x+1=+2x2+3x+1=(x+)(+)=(2x+1)(x+1)x5+x3+x2+1

1

0x4+x2+x-1x+1

01

1-x

xx3-x2+2x-10因此(f(x),g(x))=x+1=(1)(x5+x3+x2+1)+(-x)(x4+x2+x-1)m(x)=1v(x)=-x3、求二元域上多項(xiàng)式的最大公因式(f(x),g(x))，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+1.答：用輾轉(zhuǎn)相除法計(jì)算如下x5+x3+x2+1=x(x4+x2+1)+x2+x+1x4+x2+1=(x2+x+1)(x2+x+1)因此(f(x),g(x))=x2+x+14、f(x),g(x)?F2[x]且有f(x)=x6+x5+x4+x3,g(x)=x5+x2+x+1.求m(x)和n(x)，使得(f(x),g(x))=m(x)f(x)+g(x)n(x)。答：由列表法可求出(f(x),g(x))的公因子及相應(yīng)系數(shù)組合，如表6所示：表6求(f(x),g(x))的公因子及相應(yīng)的系數(shù)組合u(x)

v(x)

qx6+x5+x4+x3

1

0x5+x2+x+1

0

1

x+1x4+1x2+1

1x

x+1x2+x+1

xx2+10因此(f(x),g(x))=x2+1=x(x6+x5+x4+x3)+(x2+x+1)(x5+x2+x+1)m(x)=xv(x)=x2+x+15.求有理數(shù)域上多項(xiàng)式的最大公因式（f(x),g(x)），其中f(x)=x5+x4+x2+2x+1,g(x)=x4+x3+x2+2x+1.答：(f(x),g(x))=x+1。6.求有理數(shù)域上多項(xiàng)式的最大公因式（f(x),g(x)），并計(jì)算u(x),v(x)，使得(f(x),g(x))=u(x)f(x)+v(x)g(x)，其中f(x)=x5+x3+x2+1,g(x)=x4+x2+x-1.答：x+1=f(x)-xg(x)。三、標(biāo)準(zhǔn)分解和最小公倍數(shù)1.[288，392]＝14112

。2．12600的標(biāo)準(zhǔn)分解式是_

2332527

。3.547是_

___.（填“素?cái)?shù)”或“合數(shù)”）。3528的標(biāo)準(zhǔn)分解式是_2^3*3^2*7^2___。4.計(jì)算以下數(shù)組的最小公倍數(shù)。(1)[1046,697](2)[20301044](3)[195,72,90](4)[2104,2720,1046]，，解：(1)由第2題計(jì)算得(1046,697)=1，因此[1046,697]=1046?697=729062。(2)由第2題計(jì)算得(20301044)=58，因此[20301044]=2030?1044?58=36540。(3)由輾轉(zhuǎn)相除法可計(jì)算得(195,72,90)=3，因此[195,72,90]=195?72?90?3=4680(4)由第3題計(jì)算得(2104,2720,1046)=2，因此[2104,2720,1046]=2104?2720?1046?2=374133280。5.求正整數(shù)a,b，使得a+b=120,(a,b)=24,[a,b]=144。答：由a+b=120及ab=(a,b)[a,b]=24?144=3456解得a=48b,=a=72,b=48。6.設(shè)a,b是正整數(shù)，證明：(a+b)[a,b]=a[b,a+b]。

7或2答：只須證(a+b)

abb(a+b)(a,b)(b,a+b)

，即只須證(b,a+b)=(a,b)此式顯然。7.寫(xiě)出下列數(shù)的的標(biāo)準(zhǔn)分解式。(1)

22345680(2)166896912(3)22345680解：(1)

22345680=24?3?5?7?47?283。448.判斷561與967是否為素?cái)?shù)。解：由3|561，所以561不是素?cái)?shù)，由2,3,是素?cái)?shù)。

967，，=a(2)166896912=2?3?，，=a(2)166896912=2?3?7?13?19?2011。(3)22345680=2?3?5?7?47?283。,殛都不能整除967，所以967四、其他類(lèi)型題1.證明：若m-p?mn+pq，則m-p?mq+np。答：由恒等式mq+np=(mn+pq)-(m-p)(n-q)及條件m-p?mn+pq可知m-p?mq+np。2.證明：任意給定的連續(xù)39個(gè)自然數(shù)，其中至少存在一個(gè)自然數(shù)，使得這個(gè)自然數(shù)的數(shù)字和能被11整除。答：在給定的連續(xù)39個(gè)自然數(shù)的前20個(gè)數(shù)中，存在兩個(gè)自然數(shù)，它們的個(gè)位數(shù)字是0，其中必有一個(gè)的十位數(shù)字不是9，記這個(gè)數(shù)為a，它的數(shù)字和為s，則a,a+1,L,a+9,a+19的數(shù)字和為s,s+1,L,s+9,s+10，其中必有一個(gè)能被11整除。3.設(shè)a，b是正整數(shù)，證明：(a+b)[a,b]=a[b,a+b]。答：只須證(a+b)

ab(a,b)

=a

b(a+b)(b,a+b)

，即只須證(b,

a+b)=(a,b)，此式顯然。4.求正整數(shù)a，b，使得a+b=120，(a,b)=24，[a,b]=144。答：由a+b=120及ab=(a,b)[a,b]=24?144=3456解得a=48，b=72或a=72，b=48。5.計(jì)算2050與3768的二進(jìn)制表示和十六進(jìn)制表示。解：2050的二進(jìn)制表示：2050=(100000000010)22050的十六進(jìn)制表示：2050=(802)163768的二進(jìn)制表示：3768=(111010111000)23768的十六進(jìn)制表示：3768=(EB8)166.證明6|n(n+1)(2n+1)，其中n為任意整數(shù)。證明：n(n+1)(2n+1)=n(n+1)(n-1+n+2)=(n-1)n(n+1)+n(n+1)(n+2)；(n-1),n,(n+1)是連續(xù)三個(gè)整數(shù)，其中必有一個(gè)是3的倍數(shù)，至少有一個(gè)是2的倍數(shù)，因此6|(n-1)n(n+1)，同理6|n(n+1)(n+2)，因此6|n(n+1)(2n+1)。7.證明：若m-p|mn+pq，則m-p|mq+np。答：由恒等式mq+np=(mn+

p)q-(

m)p-及qm-p|mn+pq條件可知m-p|m+n。8.證明：任意給定的連續(xù)39個(gè)自然數(shù)，其中至少存在一個(gè)自然數(shù)，使得這個(gè)自然數(shù)的數(shù)字和能被11整除。答：在給定的連續(xù)39個(gè)自然數(shù)的前20個(gè)數(shù)中，存在兩個(gè)自然數(shù)，它們的個(gè)位數(shù)字是0，其中必有一個(gè)的十位數(shù)字不是9，記這個(gè)數(shù)為a，它的數(shù)字和為s，則a,a+1,L,a+9,a+19的數(shù)字和為s,s+1,L,s+9,s+10，其中必有一個(gè)能被11整除。第二章同余方程重點(diǎn)內(nèi)容：同余的性質(zhì)、完全剩余系、模逆運(yùn)算、模冪運(yùn)算（利用歐拉定理進(jìn)行降冪，再用從右向左或者從左向右算法計(jì)算）、一次同余方程求解一、同余性質(zhì)（剩余系）1.將612-1分解成素因數(shù)之積。答：612-1=5?7?13?31?37?43?97。2.①寫(xiě)出完全剩余系和簡(jiǎn)化剩余系（縮系）的概念，并舉例說(shuō)明（3分）；②寫(xiě)出154440的標(biāo)準(zhǔn)分解式（7分）。3.證明：1978103-19783能被103整除。答：因103=2353，顯然1978103-19783?0(mod23)，再由1978100?1(mod53)得1978103-19783?0(mod53)，故1978103-19783?0(mod103)。-(n)-(n)qp4.

證明：對(duì)于任意的整數(shù)a，(a,561)=1，都有a560?1(mod561)，但561是合數(shù)。答案：因561=3?11?17，對(duì)于一切整數(shù)a，(a,561)=1，有(a,3)=1，(a,11)=1，(a,17)=1，由費(fèi)馬定理可得a560=(a2)280?1(mod3)，a560=(a10)56?1(mod11)，a560=(a16)35?1(mod17)，故a560?1(mod561)。5.一般地，模10的最小非負(fù)完全剩余系為{0,1,2,3,4,5,6,7,8,9}；模10的簡(jiǎn)化剩余系為（或縮系）

{1,3,7,9}。6．一般地，模6的最小非負(fù)完全剩余系為

；模6的簡(jiǎn)化剩余系為（或縮系）

。7．φ(120)-φ(100)＝________。2．φ(100)-φ(72)＝___16_______。8．一般地，模8的最小非負(fù)完全剩余系為{0,1,2,3,4,5,6,7}；模8的簡(jiǎn)化剩余系為（或縮系）{1,3,5,7}。9.寫(xiě)出模15，24的縮系。答：15的縮系為{1,2,4,7,8,11,13,14}；24的縮系為{1,5,7,11,13,17,19,23}。10.求19，27，40的歐拉函數(shù)值。答：j(19)=19-1=18；13112511.若(m,n)=1，證明：mj(n)+nj(m)?1(modmn)。證明：可將mn分解列出方程如下：祜mj(n)+nj(m)?0+1?1(modm)鐿m+n?1+0?1(modn)

?mj(n)+nj(m)?1(modmn)12.證明：對(duì)于任意正整數(shù)m有

?d|m,d>0

f(d)=m。?j(n)j(m)?j(n)j(m)證明：當(dāng)n=1時(shí)，?f(d)=1，設(shè)n=p1ad|n

pka，則?f(d)=?f(d1)d|n

?dk1|pkk

f(dk)=[1+(p1-1)+

+(p1a1-p1a1-1)][1+(pk-1)+

+(pkak-pkak-1)]=p1a1

pkak=n。13.設(shè)m與n是正整數(shù)，證明：j(mn)j((m,n))=(m,n)j(m)j(n)。證明：設(shè)m=p1a1

pkakm1，n=p1b1

pkbkn1，pi

/m1，pi/n1，(m1,n1)=1，則11

pak+bkm1n1)=pa1+b1

ki=1

1pi

)f(m1)f(n1)，11

ki=1

1pi

)，由此得ki=1

1pi

)f(m1)pbki=1

1pi

)f(n1)=(m,n)j(m)j(n)。14證明：70!?61!(mod71)。證明：由題得只需證明7?0-(9?8??1)?，因此得證。71)

6?9?

6?2

1，(即mod71)二、模冪運(yùn)算242.求313159被7除的余數(shù)。答：313159=6(mod7)。3.簡(jiǎn)述一種簡(jiǎn)便模冪運(yùn)算（從右向左或從左向右計(jì)算）的思路。（10分）5134.歐拉函數(shù)j(7)=

6

10

mod7。2005年7月26日是星期二，問(wèn)此天后第21000天是星期幾？d1|p11||pkak+bk?(1-k1pkmin{ak,bk})=(m,nd1|p11||pkak+bk?(1-k1pkmin{ak,bk})=(m,n)?(1-pka?(1-pkb?(1-11(mod1.寫(xiě)出歐拉定理和費(fèi)馬小定理（3分），用這兩個(gè)定理計(jì)算5mod21（7分）。至少用兩種方法計(jì)算79(mod315)。（共20分），利用歐拉定理計(jì)算1010=4解

依題意，我們需要求21000mod7，即整數(shù)21000模7的最小非負(fù)剩余。因10003333因此，第21000天是星期四。5.3408寫(xiě)成十進(jìn)制時(shí)的最后兩位數(shù)是61

。6．運(yùn)用從左向右（或從右向左）的算法計(jì)算：2567mod61。答案：(2,61)=1，j(61)=60,567=60?9+27，56727用從左向右計(jì)算方法，有27的二進(jìn)制表示11011，列表格計(jì)算如下：5677.用歐拉定理求下列模冪運(yùn)算。246

mod8答：

1851

mod15(1)(2)

j(8)=4，因此3246?3246(mod4)?32?1mod8。j(15)=8，因此51851?51851(mod8)?53?5mod15。解答：

1025

mod15根據(jù)a

f(m)

?1(modm)計(jì)算得出31025?3(mod15)9.用快速算法求下列模冪運(yùn)算。33ikiiki312^2×2=8208^2=3113^2×2=180118^2×2=38為23mod7=1，所以2mod7為23mod7=1，所以2mod7=(2999?2)mod7=((2)mod7?2mod7)mod7=2，所以2mod61=2mod61，2mod61=38(1)3(2)58.計(jì)算3(1)13mod4758答：(1)33的二進(jìn)制表示：100001(2)58的二進(jìn)制表示：111010三、模逆運(yùn)算1、求35(mod41)的乘法逆元。-1393539?34(mod41)。2、求23(mod1800)的乘法逆元。答：利用擴(kuò)展歐幾里德輾轉(zhuǎn)相除法列表計(jì)算如下：v

q1800

0ikix40213≡28ikix40213≡2830228≡3220232≡3710237≡60126×13≡45iikix41211×11≡5831258×11≡2020220≡6511265×11≡4400244≡60(2)11mod67(2)11mod67答：35(mod41)?35j(41)-1?35(mod41)，利用模冪快速算法可計(jì)算得23651

1-78235-313

783150因此23-1?-313?1487(mod1800)。3、求11(mod26)的乘法逆元解答：26=11?2+44=26-11?211=4?2+33=11-4?2=11-（26-11?2）?2=-2?26+5?114=3?1+11=4-3?1=（26-11?2）-（-2?26+5?11）?1=3?26-7?11-14、求5(mod14)的乘法逆元解答：14=5?2+45=4+11=5-4=5-（14-5?2）=5?3-14即5?3=14?1+15、用歐幾里得算法計(jì)算1234mod4321的乘法逆元解答：QX1X2X3Y1Y2Y31043210112343011234QX1X2X3Y1Y2Y310432101123430112341-361911-3619-146151-146152-741532-74-307107541-30710752309-10821即11(mod26)即11(mod26)?-7(mod26)?19?5(mod14)?34321-1082=3239-1解答：由歐拉定理，有15?73?343(mod17)?73?3(mod17)?715?5(mod17)?715?5(mod17)。∴7-1?5(mod17)。四、一次同余方程求解1．同余方程15x≡12(mod99)關(guān)于模99的解是___14\47\80________。2.解同余方程：(1)6x?2(mod9)；(2)31x?5(mod17)；(3)3215x?160(mod235)。答：(1)因?yàn)?6,9)=3/|2，因此同余式6x?2(mod9)無(wú)解；(2)由(31,17)=1，因此x?(31)-1?5(mod17)x?11?5(mod17)x?4(mod17)(3)由(3215,235)=5|160，因此方程有5個(gè)解，先求一個(gè)解：643x?32(mod47)x?(643)-1?32(mod47)x?25?32(mod47)x?1(mod47)因此，5個(gè)解為xi?1+47i(mod235),i=0,1,2,

,43.

解同余方程組：6、計(jì)算7mod1776、計(jì)算7mod177-1?7(mod17)，其中φ(17)=16?3x?1(mod10)?答：方程可化解為?x?7(mod10)?

?x?1(mod2)??x?0(mod3)?x?b1(mod5)?4.解同余方程組：?鐿x?b4(mod11)。答：x?3?462?b1+1?385?b2+1?330?b3+1?210?b4(mod2310)。解同余方程組：?x?2(mod5)??x?4(mod9)答：利用中國(guó)剩余定理方程可解得x?157(mod315)?x?8(mod15)??x?13(mod25)。答：方程等價(jià)為?x?2(mod3)??x?13(mod25)利用中國(guó)剩余定理解得：x413(mod600)。6.求解同余式組?x?2(mod9)??4x?3(mod7)解因?yàn)?-1mod5=2，4-1mod7=2，所以同余式3x?4(mod5)和4x?3(mod7)的解分別為x?3(mod5)和x?6(mod7)，?4x?3(mod15)?x?12(mod15)??x?2(mod5)?4x?3(mod15)?x?12(mod15)??x?2(mod5)?x?27(mod30)??x?b2(mod6)?x?b3(mod7)?x?3(mod7)5.解同余方程組：?x?5(mod8)?x?5(mod8)?3x?4(mod5)????因此求解原同余式組等價(jià)于求解同余式組?x?2(mod9)??x?6(mod7)m1=9,m2=5,m3=7，M1=35,M2=63,M3=45，利用乘法逆元素的性質(zhì)可以分別計(jì)算M1?,M2?,M3?為M1?=M1-1mod9=35-1mod9=8；M2?=M2-1mod5=63-1mod5=2；M3?=M3-1mod7=45-1mod7=3-1mod7=5，從而同余式組的解為x?35?8?2+63?2?3+45?5?6(mod315)，即x?560+378+1350?83(mod315)。?x?2(mod7)??x?11(mod15)?x?2(mod7)?x?5(mod9)答案：方程組等價(jià)于?鐿x?11(mod5)

，?x?1(mod5)??x?5(mod9)m=5?7?9=315，M1=63,M1-1?2mod5;M2=45,M2-1?5mod7;M3=35,M3-1?8mod93i=1=63?2?1+45?5?2+35?8?5(mod315)=86(mod315)?x?3(mod5)7.解同余方程組?2x?x?3(mod5)7.解同余方程組?2x?10(mod18).???x?2(mod3)即等價(jià)于?x?2(mod7)x??Mi-1Mibi(modm)??3x+5y?38(mod47)?x-y?10(mod47)?3x+5y?38(mod47)?x-y?10(mod47)

35x1-1y10-1?y??1-1??10??r+r?1-101??3510??081-3?+?016-18??016-18??x??6-17??38??11??y??6-1810??1?9.已知單表仿射加密變換為：c≡7m＋5（mod26），其中m表示明文，c表示密文；試對(duì)密文CZDFUHRZP解密。答案：解密變換：m?7-1(c-5)?15c+3(mod26)解密結(jié)果為HOWAREYOU。（2）’加密變換c=11m+2(mod26)，試對(duì)VMWZ解密。答案：解密變換m=11-1(c-2)(mod26)=19c+14(mod26)c1=21c2=12c3=22c4=25依次代入m1=m2=m3=m4=對(duì)應(yīng)明文：（3）已知Hill密碼（C≡MK（mod26））中明文分組長(zhǎng)度為2，密鑰K為Z26上的一個(gè)2階可逆方陣。假設(shè)明文dont所對(duì)應(yīng)的密文為ELNI，求密鑰K。答案：明文dont對(duì)應(yīng)Z26中3，14，13，19；密文ELNI對(duì)應(yīng)Z26中4，11，13，8。根據(jù)C≡MK（mod26），有K=M-1C(mod26)，即VMWVMWZ211222258．求解同余方程組：?答案：?()()()??38(mod47)?x??8．求解同余方程組：?答案：?()()()??38(mod47)?x??35??38????????(mod47)??r12??-3?r12???3510??1-101??1-101?8-1?r2??r21r??.?1-101??106-17?得??????????(mod47)。?k11??k21

-1?=????(mod26)k22??1319??138??918??411??1311??138??109??1323?10.已知：Hill體制實(shí)際上就是仿射密碼的一個(gè)特例，設(shè)n=2,密鑰為，英文字母表轉(zhuǎn)換成Z26的整數(shù)，若密文為CF，試確定該加密的明文。?2319??(mod26)，加密的明文為ID，即（8，3）。?819?11.設(shè)英文字母A，B，C，…，Z分別編碼為0，1，2，…，25。已知Hill密碼（C≡MK（mod26））?67??38??8?-3

-7??024??024??8

6??1518??1518??-3

-7??66??14

14?3鼬所以，明文M=GOOD。12.已知99?62ab427，求a與b。答：a=2，b=4。補(bǔ)充：1.計(jì)算32?9mod10解：由32?9mod10?33?7mod10?34?1mod10又由801=4?200+142.求15(mod26)的乘法逆元k12??314??411?=????(mod26)=??(mod26)k12??314??411?=????(mod26)=??(mod26)解：K-1=?中明文分組長(zhǎng)度為2，密鑰K=瓏鼢，密文為AYPS，求明文M。答案：K－1=瓏鼢，C=瓏鼢，M=CK－1=瓏鼢瓏鼢=瓏?，?3801=34?100+1=(3)200?3?1?3mod(10)=3(mod10)解：(15,26)=1?存在乘法逆元26=1?15+1115=1?11+411=2?4+34=1?3+1?1=4-3=4-(11-2?4)=3?4-11=3?(15-11)-11=3?15-4?11=3?15-4?(26-15)=7?15-4?26所以15(mod26)的乘法逆元為73.求11(mod26)的乘法逆元解：(11,26)=1?存在乘法逆元26=1?11+411=2?4+34=1?3+1?1=4-3=4-(11-2?4)=3?4-11=3?(26-2?11)-11=3?26-7?11又-7?19(mod26)?11(mod26)的乘法逆元為194.求同余方程9x?12(mod15)的解解:gcd(9,15)=3?a'=

91512334==3,m'==5,b'==4又由3-1?2(mod5)?x?2?4+k?5(mod15),k=0,1,2?同余方程9x?12(mod15)的解為8,13,35.求解下列一元一次同余方程(1)3x?2(mod7)(2)9x?12(mod15)(3)7x?1(mod31)(4)20x?4(mod30)(5)17x?14(mod21)(6)64x?83(mod105)(7)128x?833(mod1001)(8)987x?610(mod1597)(9)57x?87(mod105)(10)49x?5000(mod999)解：(1)x?3(mod7)(2)x?3(mod5)(3)x?9(mod31)(4)none(5)x?7(mod21)(6)x?62(mod105)(7)x?812(mod1001)(8)x?1596(mod1597)(9)x?31(mod35)(10)x?836(mod999)6.求解下列一元一次同余方程組(1)x?1(mod4),x?2(mod3),x?3(mod5);(2)x?4(mod11),x?3(mod17);(3)x?2(mod5),x?1(mod6),x?3(mod7),x?0(mod11);(4)3x?1(mod11),5x?7(mod13);(5)8x?6(mod10),3x?10(mod17);(6)x?7(mod10),x?3(mod12),x?12(mod15);(7)x?6(mod35),x?11(mod55),x?2(mod33).解：(1)利用中國(guó)剩余定理，x?53(mod60)；(2)利用中國(guó)剩余定理，x?37(mod60)；(3)利用中國(guó)剩余定理，x?1837(mod2310)；?x?4(mod11)(4)原式化為：?利用中國(guó)剩余定理，x?4(mod143)；?x?2(mod5)(5)原式化為：眍x?9(mod17)利用中國(guó)剩余定理，x?77(mod85)；?x?2(mod5)??x?0(mod3)利用中國(guó)剩余定理，x?27(mod60)；?x?1(mod5)(7)原式化為：?x?0(mod11)?鐿x?2(mod3)矛盾，方程組無(wú)解。7.把同余方程化成同余方程組來(lái)解：(1)23x?1(mod140)(2)17x?229(mod1540)解:(1)140=4?5?7?23x?1(mod4)??23x?1(mod7)4(mod13)x侯(6)原式化為：3(mod4)x喉4(mod13)x侯(6)原式化為：3(mod4)x喉6(mod7)x??镲2(mod11)x??原方程可化為：231(mod5)x喉???x?3(mod4)??x?4(mod7)根據(jù)中國(guó)剩余定理，x?67(mod140)(2)1540=4?5?7?11?17x?229(mod4)?17x?229(mod5)原方程可化為：?鐿17x?229(mod11)?x?1(mod4)?x?2(mod5)化簡(jiǎn)后得??鐿x?7(mod11)根據(jù)中國(guó)剩余定理，x?557(mod1540)第三章原根計(jì)算重點(diǎn)概念：階、原根、指數(shù)重點(diǎn)內(nèi)容：原根存在性問(wèn)題和基本計(jì)算方法一、階、原根、指數(shù)1.①寫(xiě)出階、原根、指數(shù)的定義（2分）；②求整數(shù)13模41的階ord41(13)（8分）。整數(shù)5模17的階ord17(5)=

16

。2.設(shè)整數(shù)m=7，這時(shí)j(7)=6。計(jì)算階如下：a1a123456ordm(a)136362化簡(jiǎn)后得??x化簡(jiǎn)后得??x?2(mod5)?17x?229(mod7)?x?4(mod7)?因此，3，5是模7的原根，但1，2，4，6不是模7的原根。3.設(shè)整數(shù)m=10=2?5，這時(shí)j(10)=4。我們有因此3，7是模10的原根，但1，9不是模10的原根。4.設(shè)m>1是整數(shù)，a是與m互素的正整數(shù)，則存在整數(shù)d使得ad?1(modm)成立的充分必要條件是ordm(a)|d。證明：充分性設(shè)ordm(a)|d，那么存在整數(shù)k使得d=k?ordm(a)，因此，我們有ad=(aordm(a)

k

?1(modm)。必要性如果ordm(a)|d不成立，則由歐幾里得除法可知，存在整數(shù)q,r，使得d=q?ordm(a)+r,0<r<ordm(a)，從而ar=ar(aordm(a)

q

?ad?1(modm)，這與ordm(a)的最小性矛盾，故ordm(a)|d，證畢。5.求整數(shù)5模17的階ord17(5)。x算得到124816ord17(5)=16。這說(shuō)明5是模17的原根。6.設(shè)m>1是整數(shù)，a是與m互素的正整數(shù)，s,t是兩個(gè)正整數(shù)。假如ordm(a)=s?t，那么ordm(as)=t。解：(as)t?astmodm?1，所以ordm(as)|t，假設(shè)存在0<t'<t，使得ordm(as)=t'，aa1379ordm(a)1442))解：j))解：j(17)=16，16的因子有1,2,4,8,16，將這些因子代入5mod17，依次計(jì)5mod17?5,5mod17?8,5mod17?13,5mod17?-1,5mod17?1,所以5模17的階則有(as)t'?ast'modm?1，即ordm(a)=s?t'<s?t，與題設(shè)矛盾，得證。7.設(shè)p是一個(gè)奇素?cái)?shù)，并且

p-12

也是一個(gè)奇素?cái)?shù)，設(shè)a是與p互素的正整數(shù)，如果p-1則a是模p的原根。

a?1,a2?1,a

2

?1(modp)，證明：

由推論4-1知道ordp(a)|j(p)，因?yàn)閍?1,a2?1,a

p-12

?1(modp)，，因?yàn)閜是一個(gè)奇素?cái)?shù)，并且也是一個(gè)奇素?cái)?shù)，所22p-12的原根。8.設(shè)a-1modm為a關(guān)于模m的乘法逆元素，則ordm(a-1modm)=ordm(a)；d-1ordm(a-1modm)=ordm(a)。9.1=a0,a,a2,L,aord(a)-1模m兩兩不同余，特別地，當(dāng)a是模m的原根，即ordm(a)=j(m)時(shí)，這j(m)個(gè)數(shù)組成模m的簡(jiǎn)化剩余系；證明：首先，兩個(gè)集合中元素個(gè)數(shù)相同；其次，因?yàn)楫?dāng)a是模m的原根，所以二者互素，即1=a0,a,a2,L,aord(a)-1都和m互素，且模m不同余。所以?xún)蓚€(gè)集合等價(jià)。10.ad?ak(modm)的充分必要條件是d?k(modj(m))；？？？證明：利用反證法證明必要性，充分性顯然。11.ordm(ad)=

ordm(a)(ordm(a),d)

,d?0，進(jìn)一步，如果g是模m的原根，則gd是模m的原根的充分必要條件是(f(m),d)=1；證明：設(shè)r=(ordm(a),d)，ordm(ad)=n，那么(ad)n=adn=1，根據(jù)定理1有ordm(a)|dn，因此

|rr

ordm(a)drr

ordm(a)r

|n。所以ordp(a)=/1,2,p-1p所以ordp(a)=/1,2,p-1p-1,p-1，從而ordp(a)=j(p)=p-1，即a是模p以j(p)只有四個(gè)正因數(shù)1,2,證明：對(duì)于任意整數(shù)d，總有(a-1)modm=(ad)modm式子成立，所以ordm(a)dn，又因?yàn)?,)=1，因此顯然有(ad)

ordm(a)r

=1，根據(jù)定理1有n|

ordm(a)r

。因此ordm(ad)=

ordm(a)(ordm(a),d)

。如果g是模m的原根，ordm(g)=j(m)，此時(shí)有g(shù)d是模m的原根?ord(gd)=

j(m)(j(m),d)

=j(m)?(j(m),d)=1。12.如果模m存在一個(gè)原根g，則模m有j(j(m))個(gè)不同的原根；證明：由性質(zhì)（5）可得。13.如果(a,m)=1,(b,m)=1，則(ordm(a),ordm(b))=1的充分必要條件是ordm(ab)=ordm(a)?ordm(b)；證明：根據(jù)定理1，可得(a)?ord(b)ord(ab)當(dāng)ordm(b)|ordm(ab)ordm(a)時(shí)，(ordm(a),ordm(b))=1?ordm(b)|ordm(ab)，同理可證，當(dāng)ordm(a)|ordm(ab)ordm(b)

時(shí)，(ordm(a),ordm(b))=1?ordm(a)|ordm(ab)，命題得證。14.若n|m，則ordn(a)|ordm(a)；證明：因?yàn)閍ord(a)=1modm，因此m|aord(a)-1，又因?yàn)閚|m，存在正整數(shù)q，使得m=nq，因此nq|aord(a)-1，因此n|aord(a)-1，因此aord(a)=1modn，再根據(jù)定理1即得ordn(a)|ordm(a)。15.若(m,n)=1，則ordmn(a)=[ordm(a),ordn(a)]；證明：因?yàn)閍ord(a)=1modm,aord(a)=1modn，因此a[ord(a),ord(a)]=1modm，(a),ord(a),ord定理1，有ordmn(a)|[ordm(a),ordn(a)]。因?yàn)閍ord(a)=1modmn，且(m,n)=1，因此aord(a)=1modm，aord(a)=1modn，因此ordm(a)|ordmn(a),ord(a)|ord(，=aord(a)?ord=aord(a)?ord(b)(a)?ordabordbord(b)=1?ordm(ab)|ordm(a)?ordm(b)又(ab)=1?(ab)ord(ab)ord(a)=bord(ab)ord(a)=1?ordmmm(a)(b)|ord(ab)orda[ord(a)]=1modn，又因?yàn)?m,n)=1，因此有a[ord(a)]=1modmn，根據(jù)nmna)因此[ordm(a),ordn(a)]|ordmn(a)。命題得證。16.(1)若(m,n)=1，(a1,mn)=1，(a2,mn)=1，則存在整數(shù)a，使得ordmn(a)=[ordm(a1),ordn(a2)]；(2)若(a,m)=1,(b,m)=1，則存在整數(shù)c，使得ordm(c)=[ordm(a),ordm(b)]。證明：對(duì)于整數(shù)ordm(a)和ordm(b)，存在整數(shù)u,v，滿(mǎn)足：u|ordm(a)，v|ordm(b)，(u,v)=1，使得uv=[ordm(a),ordm(b)]，現(xiàn)在令s=

ordm(a)u

，t=

ordm(b)v

，有ordm(as)=

ordm(a)(ordm(a),s)

=u，ordm(bt)=

ordm(b)(ordm(b),t)

=v，ordm(asbt)=ordm(as)?ordm(bt)=uv=[ordm(as),ordm(bt)]，因此，取c?asbt(modm)即為所求。17.設(shè)整數(shù)m=21=3?7，這時(shí)j(21)=12。我們有因此，模21沒(méi)有原根。然后給出原根存在的一個(gè)充分必要條件：二、階的計(jì)算1.計(jì)算階ord18(5)和ord17(5)。a12a1245810111316171920ordm(a)163626623662答案：j(1=8)，66

的因子有

1,2,3,6，計(jì)算52

3

7=,5

6

mod18

1因?yàn)閖(17)=16，16的正因數(shù)為1，2，4，8，16。計(jì)算51?5(mod17)，52?8(mod17)，54?13(mod17)，58?-1(mod17)，516?1(mod17)所以ord17(5)=16。2.計(jì)算階ord99(91)。2算2345

，所以ord99(91)=5。3.計(jì)算階ord127(31)。答案：j(127)=126=2?3?21，126的因子有2,3,6,21,42,63，計(jì)算2642所以ord127(31)=63。4.計(jì)算階ord128(3)。答案：j(128)=64，64的因子有2,4,8,16,32，計(jì)算216所以ord128(3)=32。5.

已知2是模11的原根.（1）求ind（23）,ind（210）.解：a

0

1

2

3

4

5

6

7

8

9mo=d18mod，=所以8ord181(5)7=6,mo=d18mod，=所以8ord181(5)7=6,；51答案：j(99)=j(3)j(11)=60，60的因子有1,2,3,4,5,6,10,12,15,20,30，計(jì)91mod99?(-8)2?64,(-8)mod99?(-17),(-8)mod99?37,(-8)mod99?131mod127?72，3mod127?73，3131mod127?122，21mod127?19，3131mod127?107，63mod127?1313mod128?9，4mod128?81，33mod128?65，32mod128?1，3a

1

2

4

8

5

10

9

7

3

6有上表格可得ind（23）=8，ind（210）=5（2）ind

42mod（11-1）的值解：∵42=6?7，且11/|7?6∴ind42?ind7+ind6(mod11-1)即得ind42?16mod(11-1)。三、原根的計(jì)算1.設(shè)m>1，j(m)的所有不同素因數(shù)是q1,q2,L,qk，則g是模m的一個(gè)原根的充分必要條件是j(m)g

qi

?1(modm),i=1,2,L,k。證

必要性

若g是模m的一個(gè)原根，則ordm(g)=j(m)，但是0<

j(m)qi

<j(m)，故g

j(m)qi

?1(modm),i=1,2,L,k成立。j(m)充分性

若條件g

qi

?1(modm),i=1,2,L,k成立，假設(shè)ordm(g)<j(m)，由階的性質(zhì)可以知道ordm(g)|j(m)，所以

j(m)ordm(g)

是大于1的正整數(shù)，所以存在j(m)的某個(gè)素因數(shù)qi，使得qi|

j(m)ordm(g)

，即存在整數(shù)s使得

j(m)ordm(g)

=qis，即所以

j(m)qij(m)

=ordm(g)?s，g

qi

?1(modm)，與假設(shè)條件矛盾。所以ordm(g)=j(m)，即g是模m的一個(gè)原根。2.求模41的所有原根。解因?yàn)閖(41)=40=23?5，所以40的素因數(shù)為2，5，而40/2=20，40/5=8，2(mod)112(mod)11由原根定義只需驗(yàn)證g8,g20模41是否為1即可，逐個(gè)計(jì)算可得：28mod41=10,220mod41=1，38mod41=1，48mod41=18,420mod41=158mod41=18,520mod41=168mod41=10,620mod41=40故6是模41的原根。根據(jù)性質(zhì)(5)和(6)，當(dāng)(d,j(41))=(d,40)=1時(shí)，6d是模41的原根，當(dāng)d遍取40的一個(gè)簡(jiǎn)化剩余系時(shí)，6d遍歷模41的所有原根，所以模41的所有原根為61mod41=6,611mod41=28,621mod41=35,631mod41=13,

63mod41=11,613mod41=24,623mod41=30,633mod41=17,

67mod41=29,617mod41=26,627mod41=12,637mod41=15,

69mod41=19,619mod41=34,629mod41=22,639mod41=7.3.求模m=412=1681的原根。解因?yàn)?是模41的一個(gè)原根，所以根據(jù)推論1的證明過(guò)程，可知6或者6+41=47是模1681的原根，事實(shí)上，我們有640mod412=143，641?20mod412=1106，641?8mod412=903；4740mod412=1518，4741?20mod412=83，4741?8mod412=370；所以6和47都是模1681的原根，它們也都是41a的原根。4.設(shè)m=2?412=3362，求模m的原根。解應(yīng)用推論2可知6+1681=1687和47都是模3362的原根。5.證明：設(shè)a對(duì)模數(shù)奇素?cái)?shù)p的階為d，d<p-1，則al，l=1,2,3,是p的原根。

,d都不證明：因?yàn)閍l(l=1,2,3,,d)對(duì)模數(shù)p的階為

d(l,d)

?d<p-1，所以al(l=1,2,3,,d)都不是p的原根。6.設(shè)a對(duì)模m的階為l，an?1(modm),n?0，則l|n。證明：如果結(jié)論不成立，則必有兩個(gè)整數(shù)q,r，使n=ql+r,0<r<lql7.設(shè)a對(duì)模m的階為l，則1,a,a2,

,al-1對(duì)模數(shù)m兩兩不同余。證明：如果結(jié)論不成立，則有某對(duì)正整數(shù)j,k,0?j<k?l-1，使aj?ak(modm),則有ak-j?1(modm),而0<k-j?l-1，這與a對(duì)模m的階為l矛盾。8.模19的原根。答案：j(19)=18=2?3?3，所以j(19)的素因數(shù)只有2，3，而1818=9,23

=6由原根定義只需驗(yàn)證g9,g6模19是否為1即可，逐個(gè)計(jì)算可得：68故2是模19的原根。根據(jù)性質(zhì)（5）和（6），當(dāng)(d,f(19))=(d,18)=1時(shí)，2d是模19的原根，當(dāng)d遍取19的一個(gè)簡(jiǎn)化剩余系時(shí)，2d遍歷模19的所有原根，所以模19的所有原根為21=2mod19，25=13mod19，27=14mod19，211=15mod19，213=3mod19，217=10mod19。9.求模59的原根。答案：229i而1?an?aql+而1?an?aql+r?aar?ar(modm)，這就和l的定義相違背。2mod19=7,2mod19=9余原根2mod59,(i,58)=1，共有j(58)=28個(gè)。10.求模61的原根。答案：j(61)=60=2?2?3?5，所以60的素因數(shù)為2，3，5，而60/2=30，60/3=20，60/5=12由原根定義只需驗(yàn)證g12,g20,g30模61是否為1即可，逐個(gè)計(jì)算可得：12