密碼學(xué)實(shí)驗(yàn)教程（第2版） 課件 第1、2章 數(shù)論基礎(chǔ)算法、有限域算法

第1章數(shù)論基礎(chǔ)算法主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1厄拉多塞篩算法

歐幾里得算法

擴(kuò)展歐幾里得算法

擴(kuò)展歐幾里得算法

快速冪取模算法

中國(guó)剩余定理中國(guó)剩余定理（ChineseRemainderTheorem,CRT）即孫子定理，是中國(guó)古代求解一次同余式組的方法，又稱中國(guó)余數(shù)定理。在《孫子算經(jīng)》中，“物不知數(shù)”的問(wèn)題如下：有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問(wèn)物幾何？中國(guó)剩余定理

Miller-Rabin素性檢測(cè)算法

主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1厄拉多塞篩算法實(shí)現(xiàn)

歐幾里得算法實(shí)現(xiàn)

擴(kuò)展歐幾里得算法實(shí)現(xiàn)

快速冪取模算法實(shí)現(xiàn)

中國(guó)剩余定理實(shí)現(xiàn)

Miller-Rabin素性檢測(cè)算法實(shí)現(xiàn)

主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1厄拉多塞篩算法測(cè)試

輪數(shù)劃去數(shù)字14，6，8，1026，9得到最終素?cái)?shù)2，3，5，7

歐幾里得算法測(cè)試

輪數(shù)ab171031023109039040440105100擴(kuò)展歐幾里得算法測(cè)試

遞歸深度31100121011-2111-2-23擴(kuò)展歐幾里得算法測(cè)試

遞歸深度4291001329011-12291-1-15擴(kuò)展歐幾里得算法測(cè)試其他測(cè)試數(shù)據(jù)3113-512124615027235156730866587042569449124260651729255751720876577542770214811199308823476528929542231719-27950388378727451425390221029736985378094362805639979599940745026457009085475842906511784400567911370961646914494888351222912350230517638593181028408890675509023843189897270890443917889846802171079840187598665712521108447262149959537125434639073838204219235039994987625167590963480899777255933775238312044097122773255647530276806317636026727679800825370459321617724871515442147432420951257037823141069640181-10760458036804375751650693175177200568160129685505522974978475222018695871408651367182921594978119495798721264716942320651123713188666821080004338197507387669427916726892264502009194458568532584907540503797044831940871001157002257559190662110275404841788698230849292994592286170075217255757058848419820263371快速冪取模算法測(cè)試

017711105209530354196快速冪取模算法測(cè)試

017711105209530354196快速冪取模算法測(cè)試其他測(cè)試數(shù)據(jù)p51000331514944626594292900478150673551714111875607517915306553722688387113047243043043961195094167745977232924742099538163720891467842744895846522520832379454230中國(guó)剩余定理測(cè)試

0,0,023,28,33924,759,6446,19,25,20,123,28,33924,759,6446,19,2283,102,2323,28,33924,759,6446,19,2

Miller-Rabin素性檢測(cè)算法測(cè)試算法的輸入為被檢測(cè)的大數(shù)，測(cè)試次數(shù)為20次,輸出為True或False。若輸出結(jié)果為True，則表示該數(shù)通過(guò)了Miller-Rabin素性檢測(cè)，很可能為素?cái)?shù)；若輸出結(jié)果為False，則表示該數(shù)不為素?cái)?shù)。輸入數(shù)據(jù)輸出檢測(cè)結(jié)果1000023False1000033True100160063False1500450271True主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1思考題（1）中國(guó)剩余定理存在多種不同的表示形式，請(qǐng)嘗試給出中國(guó)剩余定理的其他表示形式。（2）Miller-Rabin素性檢測(cè)算法并非確定性的素性判定方法，如何通過(guò)重復(fù)檢測(cè)提高該算法的可信度？試簡(jiǎn)要說(shuō)明。第2章有限域算法主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1有限域四則運(yùn)算算法

有限域四則運(yùn)算算法乘法運(yùn)算原理除法運(yùn)算原理有限域歐幾里得算法

有限域求乘法逆元算法

主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1有限域四則運(yùn)算算法實(shí)現(xiàn)

有限域四則運(yùn)算算法實(shí)現(xiàn)

有限域四則運(yùn)算算法實(shí)現(xiàn)

有限域歐幾里得算法實(shí)現(xiàn)

有限域擴(kuò)展歐幾里得算法實(shí)現(xiàn)

有限域求乘法逆元算法實(shí)現(xiàn)

主要內(nèi)容算法測(cè)試3思考題4算法實(shí)現(xiàn)2算法原理1有限域四則運(yùn)算算法測(cè)試針對(duì)各個(gè)算法，輸入兩個(gè)整數(shù)進(jìn)行測(cè)試，其中不可約多項(xiàng)式固定為0x11b有限域四則運(yùn)算輸入數(shù)據(jù)運(yùn)算結(jié)果有限域加法0x89+0x4d0xc40xaf+0x3b0x940x35+0xc60xf3有限域減法0x89-0x4d0xc40x9f-0x3b0xa40x35-0xc60xf3有限域乘法0xef0xa20x00帶余除法0xde/0xc6(0x01,0x18)0x8c/0x0a(0x14,0x04)0x3e/0xa4(0x00,0x3e)有限域歐幾里得算法測(cè)試

輸入數(shù)據(jù)0x75,0x350x01(0x01,0x19,0x3c)0xac,0x590x03(0x03,0x07,0x0f)0xf8,0x2e0x02(0x02,0x04,0x1b)0x48,0x990x09(0x0