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

《密碼學(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=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+68=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ù)線性組合。(1)1387,162(2)2046,1620解：(1)?列表法可求出(1387,162)的公因?及相應(yīng)的系數(shù)組合，如表1所?：表1求(1387,162)的公因?及相應(yīng)系數(shù)

173-6252由上表可得：(1387,162)=1=1387?73+162?(-625)。(2)?列表法可求出(2046,1620)的公因?及相應(yīng)的系數(shù)組合，如表2所?：表2求(2046,1620)的公因?及相應(yīng)的系數(shù)組合由上表可得：(2046,1620)=6=1387?(-19)+162?24。8.計(jì)算4389，5313，399的最?公因?，并把它表?為這些數(shù)的整系數(shù)線性組合。解：先求4389與5313的最?公因?，如下表3，公因?為213。再求213與399的最?公因?，如表4，公因?為21。表3求4389與5313的最?公因?表4求213與399的最?公因?+2x2+3x+1=(x+)(+)=(2x+1)(x+1)?由表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=12x(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ù)組合因此(f(x),g(x))=x+1=(1)(x5+x3+x2+1)+(-x)(x4+x2+x-1)μ(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.求μ(x)和ν(x)，使得(f(x),g(x))=μ(x)f(x)+g(x)ν(x)。答：由列表法可求出(f(x),g(x))的公因?及相應(yīng)系數(shù)組合，如表6所?：表6求(f(x),g(x))的公因?及相應(yīng)的系數(shù)組合，x4+1x2+11xx+1x2+x+1xx2+10因此(f(x),g(x))=x2+1=x(x6+x5+x4+x3)+(x2+x+1)(x5+x2+x+1)μ(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]，，=a(2)166896912=2?3?7?13?19?2011。(3)22345680=2?3?5?7?47?283。,????都不能整除967，所以967解：(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四、其他類(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,,a+9,a+19的數(shù)字和為s,s+1,,s+9,s+10，其中必有?個(gè)能被11整除。3.設(shè)a，b是正整數(shù)，證明：(a+b)[a,b]=a[b,a+b]。答：只須證(a+b)ab(a,b)=ab(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)，-(n)qp因此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,,a+9,a+19的數(shù)字和為s,s+1,,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)(m)4.證明：對(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ù)值。答：?(19)=19-1=18；13112511.若(m,n)=1，證明：m?(n)+n?(m)≡1(modmn)。證明：可將mn分解列出?程如下：m?(n)+n?(m)≡0+1≡1(modm)??m+n≡1+0≡1(modn)m(n)+n(m)≡1(modmn)12.證明：對(duì)于任意正整數(shù)m有∑d|m,d>0φ(d)=m。

d1|p11||pkαk+βk∏(1-k1pkmin{αk,βk})=(m,n)∏(1-pkαk∏(1-pkβk∏(1-11(mod1.寫(xiě)出歐拉定理和費(fèi)馬?定理（3分），?這兩個(gè)定理計(jì)算5mod21（7分）。?少?兩種?法計(jì)算79(mod315)。（共20分），利?歐拉定理計(jì)算1010=4證明：當(dāng)n=1時(shí)，∑φ(d)=1，設(shè)n=p1α1d|npkαk，則∑φ(d)=∑φ(d1)d|n∑dk1pkkφ(dk)=[1+(p1-1)++(p1α1-p1α1-1)][1+(pk-1)++(pkαk-pkαk-1)]=p1α1pkαk=n。13.設(shè)m與n是正整數(shù)，證明：(mn)((m,n))=(m,n)(m)(n)。證明：設(shè)m=p1α1pkαkm1，n=p1β1pkβkn1，pi/m1，pi/n1，(m1,n1)=1，則11pαk+βkm1n1)=pα1+β1ki=11pi)φ(m1)φ(n1)，11ki=11pi)，由此得1ki=11pi

)φ