2025年大學(xué)《數(shù)學(xué)與應(yīng)用數(shù)學(xué)》專業(yè)題庫(kù)——數(shù)論與計(jì)算機(jī)安全技術(shù)考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題3分，共15分。請(qǐng)將答案填在答題紙上對(duì)應(yīng)位置。）1.設(shè)a,b為整數(shù)，若存在整數(shù)q,r使得a=qb+r，且0≤r<|b|，則(a,b)表示的是（）。A.a除以b的商B.a除以b的余數(shù)C.a除以b的最大整數(shù)商D.a與b的最大公約數(shù)2.下列關(guān)于同余式的敘述，錯(cuò)誤的是（）。A.若a≡b(modm)，則a-b是m的倍數(shù)。B.若a≡b(modm)，則a和b除以m的余數(shù)相同。C.若a≡b(modm)，則a+c≡b+c(modm)對(duì)所有整數(shù)c成立。D.若a≡b(modm)，則a2≡b2(modm)。3.滿足同余方程2x≡3(mod5)的整數(shù)解x是（）。A.1B.2C.3D.44.已知整數(shù)n=12345，則φ(n)，即n的歐拉函數(shù)值φ(12345)，一定不是下列哪個(gè)數(shù)的倍數(shù)？（φ(n)表示小于n且與n互質(zhì)的正整數(shù)的個(gè)數(shù)。）A.1B.2C.3D.45.在RSA公鑰密碼體制中，選擇兩個(gè)大質(zhì)數(shù)p和q，計(jì)算n=pq，φ(n)=(p-1)(q-1)。為了找到模n的乘法逆元，即求私鑰d，需要滿足的條件是（）。A.d是e的模φ(n)的逆元，即de≡1(modφ(n))B.d是e的模n的逆元，即de≡1(modn)C.d是φ(n)的平方根D.d是n的平方根二、填空題（每小題4分，共20分。請(qǐng)將答案填在答題紙上對(duì)應(yīng)位置。）6.設(shè)整數(shù)a=120，b=90，則(a,b)=__________，且可以表示為a=__________b+__________。7.滿足同余方程x2≡1(mod8)的正整數(shù)解x的集合是__________。8.設(shè)n為正整數(shù)，如果存在整數(shù)k使得n=2^k-1，且n是質(zhì)數(shù)，則稱n為梅森素?cái)?shù)。若p是一個(gè)奇質(zhì)數(shù)，那么2^p-1一定是質(zhì)數(shù)嗎？請(qǐng)回答“是”或“否”。9.在RSA算法中，通常選擇e=__________作為公鑰部分，其原因是__________。10.離散對(duì)數(shù)問(wèn)題是指：已知大質(zhì)數(shù)p，模p的生成元g，以及一個(gè)整數(shù)h(1<h<p-1)，求整數(shù)x(0≤x<p-1)使得g^x≡h(modp)。請(qǐng)簡(jiǎn)述求解離散對(duì)數(shù)問(wèn)題的一般難度所在：__________。三、計(jì)算題（每小題6分，共18分。請(qǐng)寫出詳細(xì)的計(jì)算過(guò)程。）11.使用歐幾里得算法求整數(shù)135和78的最大公約數(shù)，并給出它們的貝祖等式表示形式（即找到整數(shù)x,y使得135x+78y=(135,78)）。12.設(shè)p=61是質(zhì)數(shù)，g=2是模p的生成元。求模61的逆元d，使得de≡1(mod60)，其中e=17是RSA公鑰的一部分。13.已知RSA公鑰(e,n)=(7,143)，其中n=11×13。求對(duì)應(yīng)的私鑰d。四、證明題（每小題10分，共20分。請(qǐng)給出嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明。）14.證明：若a≡b(modm)，且d是m的任一正約數(shù)，則a≡b(modd)。15.設(shè)p是質(zhì)數(shù)，a是整數(shù)，且gcd(a,p)=1。證明：存在唯一的x(0≤x<p-1)使得a^x≡1(modp)。這個(gè)x就是a模p的階，記作ord_p(a)。五、綜合應(yīng)用題（共17分。請(qǐng)結(jié)合所學(xué)知識(shí)進(jìn)行分析和解答。）設(shè)使用RSA算法進(jìn)行加密和解密，選擇質(zhì)數(shù)p=53，q=59。計(jì)算模n=pq和歐拉函數(shù)φ(n)。生成公鑰(e,n)和私鑰(d,n)。假設(shè)要加密消息M=35，求密文C。然后使用私鑰解密密文C，驗(yàn)證是否能得到原文M。在此過(guò)程中，說(shuō)明e,d,n,C各自的具體數(shù)值。試卷答案一、選擇題1.D2.D3.C4.C5.A二、填空題6.30,1,307.{1,3,5,7}8.否9.65537,計(jì)算效率高，易于編程實(shí)現(xiàn)（或因其素性已被廣泛驗(yàn)證）10.計(jì)算復(fù)雜度高，難以在合理時(shí)間內(nèi)求解（或?qū)儆陔y解問(wèn)題）三、計(jì)算題11.計(jì)算過(guò)程：135=78×1+5778=57×1+2157=21×2+1521=15×1+615=6×2+36=3×2+0所以(135,78)=3。由最后一個(gè)非零余式逆推：3=21-15×13=21-(57-21×2)×1=21×3-573=21×3-(78-57×1)×1=21×4-783=21×4-78×13=(135-78×1)×4-78×1=135×4-78×5所以x=4,y=-5。貝祖等式為：135×4+78×(-5)=3。答案：(135,78)=3,135×4+78×(-5)=3。12.計(jì)算過(guò)程：需要找到d使得17d≡1(mod60)。60=17×3+917=9×1+89=8×1+18=1×8+0逆推求d：1=9-8×11=9-(17-9×1)×1=9×2-171=(60-17×3)×2-17=60×2-17×7所以d=-7。因?yàn)橐?≤d<60，取d=60-7=53。驗(yàn)證：17×53=901=15×60+1≡1(mod60)。答案：d=53。13.計(jì)算過(guò)程：n=11×13=143。φ(n)=φ(11)φ(13)=(11-1)(13-1)=10×12=120。需要找到d使得7d≡1(mod120)。120=7×17+11=120-7×17所以d=-17。取d=120-17=103。驗(yàn)證：7×103=721=6×120+1≡1(mod120)。答案：d=103。四、證明題14.證明：已知a≡b(modm)，則存在整數(shù)k使得a=b+km。設(shè)d是m的正約數(shù)，即m=dk。將a=b+km代入，得到a=b+k(dk)=b+(k')d，其中k'=k。因此，a-b=(k')d。這表明a-b是d的倍數(shù)，即a≡b(modd)。得證。15.證明：存在性：因?yàn)間cd(a,p)=1，根據(jù)歐拉定理，有a^φ(p)≡1(modp)。設(shè)ord_p(a)=x，根據(jù)定義，x是使得a^x≡1(modp)成立的最小正整數(shù)。由a^φ(p)≡1(modp)可知，x整除φ(p)。因此，存在整數(shù)k使得φ(p)=kx。如果存在兩個(gè)不同的x1,x2(0≤x1<x2<φ(p))都滿足a^x≡1(modp)，則x1整除φ(p)，x2也整除φ(p)。但由于x1<x2，這與x是最小正整數(shù)矛盾。所以，滿足a^x≡1(modp)的最小正整數(shù)x是唯一的。唯一性已證。得證。五、綜合應(yīng)用題計(jì)算過(guò)程：1.n=p×q=53×59=3127。2.φ(n)=(p-1)(q-1)=(53-1)(59-1)=52×58=3016。3.選擇e，通常選65537（因計(jì)算效率高且素性已知），e=65537。需檢查gcd(e,φ(n))=gcd(65537,3016)=1，滿足條件。公鑰為(e,n)=(65537,3127)。4.計(jì)算私鑰d，使得de≡1(modφ(n))，即65537d≡1(mod3016)。使用擴(kuò)展歐幾里得算法：3016=65537×0+301665537=3016×21+11413016=1141×2+7341141=734×1+407734=407×1+327407=327×1+80327=80×4+780=7×11+37=3×2+13=1×3+0逆推求d：1=7-3×21=7-(80-7×11)×2=7×23-80×41=(327-80×4)×23-80×4=327×23-80×921=327×23-(407-327×1)×92=327×115-407×921=327×115-(1141-407×1)×92=327×207-1141×921=327×207-1141×92=(3016-1141×2)×207-1141×92=3016×207-1141×4061=3016×207-(65537-3016×21)×406=3016×207×407-65537×406所以d=-406。取d=3016-406=2610。驗(yàn)證：65537×2610=170119170=55×3016+1≡1(mod3016)。私鑰為(d,n)=(2610,3127)。5.加密消息M=35。計(jì)算密文C，C=M^emodn=35^65537mod3127。使用快速冪算法計(jì)算：35^1=3535^2=35×35=122535^4=1225×1225=15006251500625mod3127=297635^8=2976×2976=88545768854576mod3127=265635^16=2656×2656=70645767064576mod3127=297635^32=2976×2976=88545768854576mod3127=265635^65536=(35^32)^2=2656×2656=70645767064576mod3127=297635^65537=35×35^65536=35×2976=104160104160mod3127=2976所以C=2976。6.解密密文C=2976。計(jì)算明文M，M=C^dmodn=2976^2610mod3127。使用快速冪算法計(jì)算：2976^1=29762976^2=2976×2976=88545768854576mod3127=26562976^4=2656×2656=70645767064576mod3127=29762976^8=2976×2976=88545768854576mod3127=26562976^16=2656×2656=70645767064576mod3127=29762976^32=2976×2976=88545768854576mod3127=26562976^64=2656×2656=70645767064576mod3127=29762976^128=2976×2976=88545768854576mod3127=26562976^256=2656×2656=70645767064576mod3127=29762976^512=2976×2976=88545768854576mod3127=26562976^1024=2656×2656=70645767064576mod3127=29762976^2048=2976×2976=88545768854576mod3127=26562976^4096=2656×2656=70645767064576mod3127=29762976^8192=2976×2976=88545768854576mod3127=26562976^16384=2656×2656=70645767064576mod3127=29762976^32768=2976×2976=88545768854576mod3127=26562976^65536=(2976^32768)^2=2656×2656=70645767064576mod3127=29762610=512+256+128+64+32+8+2