楊文忠　劉淑嫻　余廣新　李偉

摘 要：針對(duì)信息安全數(shù)學(xué)基礎(chǔ)理論性太強(qiáng)，教材沒(méi)有很好融合算法設(shè)計(jì)與分析思想和信息安全數(shù)學(xué)基礎(chǔ)的概念、定理和結(jié)論，提出融合算法、編程實(shí)踐和信息安全數(shù)學(xué)基礎(chǔ)關(guān)鍵概念、定理和結(jié)論的教學(xué)模式觀點(diǎn)，經(jīng)過(guò)幾年實(shí)際檢驗(yàn)，表明這種教學(xué)模式既高了學(xué)生的學(xué)習(xí)積極性有提高了教學(xué)效果。

關(guān)鍵詞：信息安全數(shù)學(xué)基礎(chǔ)算法編程教學(xué)研究

信息安全數(shù)學(xué)基礎(chǔ)是信息安全專業(yè)的一門專業(yè)基礎(chǔ)課程，有很強(qiáng)的理論性和應(yīng)用空間，是信息安全后續(xù)專業(yè)課程現(xiàn)代密碼學(xué)、網(wǎng)絡(luò)安全等課程的基礎(chǔ)。這門課程掌握不好直接影響現(xiàn)代密碼學(xué)的學(xué)習(xí)，而現(xiàn)代密碼學(xué)又直接影響網(wǎng)絡(luò)安全和網(wǎng)絡(luò)安全編程的學(xué)習(xí)，有著多米諾骨牌式的效應(yīng)。信息安全數(shù)學(xué)基礎(chǔ)主要強(qiáng)調(diào)數(shù)論和近世代數(shù)，較為抽象，數(shù)學(xué)專業(yè)的學(xué)生學(xué)習(xí)數(shù)論和近世代數(shù)有時(shí)也會(huì)有些吃力，通過(guò)對(duì)新疆大學(xué)2011級(jí)到2014級(jí)信息安全專業(yè)的本科學(xué)生的上課情況看，有些學(xué)生在學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)課程還是有些吃力的，這些學(xué)生本來(lái)數(shù)學(xué)基礎(chǔ)就有點(diǎn)差，若再提不起興趣，就會(huì)直接導(dǎo)致后面許多課程無(wú)法同步跟上。通過(guò)對(duì)2011級(jí)到2014級(jí)學(xué)生觀察發(fā)現(xiàn)大部分學(xué)生其實(shí)喜歡動(dòng)手實(shí)踐，這可提高學(xué)生的參與度和成就感。信息安全數(shù)學(xué)基礎(chǔ)雖然理論性很強(qiáng)，但也是有規(guī)律可循，需要讓學(xué)生掌握的許多理論本質(zhì)是讓學(xué)生掌握基于這些理論背后的算法，如講解整數(shù)整除基本性質(zhì)就是為了讓學(xué)生掌握擴(kuò)展歐幾里得算法，講解同余性質(zhì)及歐拉定理等也是為了讓學(xué)生掌握模重復(fù)平方計(jì)算算法，講解一次同余式和中國(guó)剩余定理其實(shí)也是在講解其算法原理，諸如此類還很多。由于大部分學(xué)生喜歡編程，將枯燥的信息安全數(shù)學(xué)基礎(chǔ)理論模型化并提出算法實(shí)現(xiàn)需求，然后讓學(xué)生去動(dòng)手實(shí)踐，學(xué)生就不會(huì)感到數(shù)學(xué)理論和公式的枯燥，這樣大部分學(xué)生就很感興趣，也提高了學(xué)生的學(xué)習(xí)的主動(dòng)性和成就感。在2012級(jí)到2014及部分學(xué)生中經(jīng)過(guò)試點(diǎn)后，學(xué)生反映還是比較好的，有些學(xué)生的創(chuàng)造力還是很突出的，改革信息安全數(shù)學(xué)基礎(chǔ)課程，刪除較為枯燥的無(wú)用的某些數(shù)學(xué)理論，精講較為實(shí)用的理論，講透實(shí)用理論的目標(biāo)和應(yīng)用場(chǎng)合，將算法融入的信息安全數(shù)學(xué)基礎(chǔ)中可使信息安全專業(yè)學(xué)生將先前學(xué)習(xí)的程序設(shè)計(jì)及數(shù)據(jù)結(jié)構(gòu)與信息安全數(shù)學(xué)基礎(chǔ)銜接在一起，支撐起后續(xù)課程的學(xué)習(xí)，又鍛煉的學(xué)生的算法設(shè)計(jì)和編程能力。因而很有必要改革傳統(tǒng)信息安全數(shù)學(xué)基礎(chǔ)課程的上課模式及授課內(nèi)容，切實(shí)讓學(xué)生能夠?qū)W得輕松也能讓學(xué)生學(xué)有所成。[1]

一、教學(xué)現(xiàn)狀

國(guó)外許多大學(xué)如麻省理工、斯坦福大學(xué)等都開(kāi)設(shè)有密碼學(xué)課程，他們大都將密碼學(xué)課程分為兩個(gè)學(xué)期，前一個(gè)學(xué)期主要講解密碼學(xué)基礎(chǔ)，即信息安全數(shù)學(xué)基礎(chǔ)，他們留有大量有關(guān)信息安全數(shù)學(xué)基礎(chǔ)的實(shí)踐項(xiàng)目，以幫助學(xué)生更好的掌握有關(guān)理論及如何應(yīng)用，開(kāi)闊學(xué)生的視野。國(guó)內(nèi)上海交通大學(xué)將信息安全數(shù)學(xué)基礎(chǔ)也分為兩個(gè)學(xué)期上，但主要是強(qiáng)調(diào)其數(shù)學(xué)基礎(chǔ)和數(shù)學(xué)理論，山東大學(xué)有著數(shù)學(xué)上的優(yōu)勢(shì)，他們的信息安全數(shù)學(xué)基礎(chǔ)就是從數(shù)學(xué)角度來(lái)傳授的，武漢大學(xué)和華中科技大學(xué)也沒(méi)有將算法有關(guān)思想融入到信息安全數(shù)學(xué)基礎(chǔ)中。緊跟國(guó)家和自治區(qū)經(jīng)濟(jì)和政治的需要，2006年新疆大學(xué)信息科學(xué)與工程學(xué)院開(kāi)設(shè)信息安全專業(yè)。2012年信息安全專業(yè)被批準(zhǔn)為自治區(qū)緊缺專業(yè)，2017年獲批為新疆維吾爾自治區(qū)戰(zhàn)略新興專業(yè)。雖然開(kāi)設(shè)了信息安全專業(yè)，但與內(nèi)地高校的生源質(zhì)量還是有些差距，鑒于信息安全專業(yè)學(xué)生的數(shù)學(xué)功底，在信息安全專業(yè)學(xué)生中主要傳授信息安全數(shù)學(xué)基礎(chǔ)背后的算法，而不是大力強(qiáng)化理論，會(huì)使以后更多信息安全專業(yè)學(xué)生受益。閆璽璽[1]提到教師是課堂教學(xué)的策劃者，要上好信息安全數(shù)學(xué)基礎(chǔ)這門課，教師必須針對(duì)該課程的特點(diǎn)和內(nèi)容，制訂好教學(xué)方案，激發(fā)學(xué)生的興趣，提高學(xué)生的積極性，為密碼學(xué)技術(shù)的學(xué)習(xí)打好基礎(chǔ)。但沒(méi)有提到融合算法和信息安全數(shù)學(xué)基礎(chǔ)基本定理和結(jié)論。李瑞琪[2]提出了信息安全數(shù)學(xué)基礎(chǔ)教學(xué)應(yīng)該“講一練二考三”，即精講、多練、廣考來(lái)提高學(xué)生學(xué)習(xí)積極性，仍然沒(méi)有解決學(xué)生算法、數(shù)據(jù)結(jié)構(gòu)、編程和信息安全數(shù)學(xué)基礎(chǔ)的知識(shí)綜合應(yīng)用問(wèn)題。秦艷琳[3]提出要精心設(shè)計(jì)課堂互動(dòng)，提高學(xué)生學(xué)習(xí)興趣和注重介紹數(shù)學(xué)基礎(chǔ)知識(shí)在密碼學(xué)和信息安全領(lǐng)域中的應(yīng)用實(shí)例，突出了信息安全數(shù)學(xué)基礎(chǔ)在密碼學(xué)中的應(yīng)用實(shí)例，但沒(méi)有將學(xué)生可能已經(jīng)具備的算法、數(shù)據(jù)結(jié)構(gòu)、編程能力綜合利用進(jìn)一步引導(dǎo)學(xué)生綜合應(yīng)用所學(xué)知識(shí)能力和提高學(xué)生自主學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)中枯燥的定理和結(jié)論能力。本文主要探索了信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)定理和結(jié)論如何與算法結(jié)合在一起，基于這些定理如何設(shè)計(jì)算法及這些定理可以現(xiàn)在算法什么地方，為進(jìn)一步探索多課程交叉融合的信息安全數(shù)學(xué)基礎(chǔ)教學(xué)模式提供了思路。[2]

二、融合算法的教學(xué)模式

從本科專業(yè)培養(yǎng)方案上來(lái)說(shuō)應(yīng)該在信息安全數(shù)學(xué)基礎(chǔ)之前開(kāi)設(shè)程序設(shè)計(jì)語(yǔ)言課程如C語(yǔ)言、Python語(yǔ)言等、線性代數(shù)、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析等課程。學(xué)生有一定的編程基礎(chǔ)后，再學(xué)習(xí)信息安全數(shù)學(xué)基礎(chǔ)理論時(shí)，就可以使用有關(guān)數(shù)據(jù)結(jié)構(gòu)和編程語(yǔ)言實(shí)現(xiàn)擴(kuò)展歐幾里得、模重復(fù)平方、原根等的具體計(jì)算，當(dāng)編寫出相應(yīng)的程序后，學(xué)生比較有成就感和獲得感，又鍛煉了學(xué)生編程能力，使學(xué)生體會(huì)到信息安全數(shù)學(xué)基礎(chǔ)不僅可以從數(shù)學(xué)角度去理解和計(jì)算也可以從計(jì)算機(jī)科學(xué)的計(jì)算角度去理解和計(jì)算。其次應(yīng)該設(shè)置信息安全數(shù)學(xué)基礎(chǔ)課程實(shí)踐課程?？梢栽O(shè)置廣義歐幾里得算法、模重復(fù)平方算法、一次同余式求解算法、中國(guó)剩余定理算法、勒讓德符號(hào)計(jì)算算法、原根求解算法、Miller-Rabin算法和有限域構(gòu)造算法等，每個(gè)算法實(shí)踐大約4學(xué)時(shí)，涵蓋了信息安全數(shù)學(xué)基礎(chǔ)主要概念、定理和結(jié)論[4]等。若無(wú)法在信息安全數(shù)學(xué)基礎(chǔ)課時(shí)內(nèi)安排實(shí)踐課程，可以安排為實(shí)踐類課程作業(yè)。學(xué)生除了需要進(jìn)行實(shí)踐外，應(yīng)該理解廣義歐幾里得算法和模重復(fù)平方算法等算法設(shè)計(jì)思想和計(jì)算機(jī)復(fù)雜度，理解為什么可以將廣義歐幾里得算法和模重復(fù)平方算法等算法應(yīng)該密碼理論中，從算法角度理解這些迭代算法的循環(huán)不變式[5]其實(shí)就是信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)定理的體現(xiàn)。[3]

三、具體實(shí)例

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

歐幾里得除法是a，b是兩個(gè)整數(shù)，其中b>0，則對(duì)任意的整數(shù)c，存在唯一的整數(shù)q，r使得a=q·b+r 。擴(kuò)展或廣義歐幾里得除法主要求兩個(gè)整數(shù)a，b的最大公約數(shù)的。即，gcd（a，b）=（a，b）= s·a+ t·b，其中最大公約數(shù)（a，b）、整數(shù)s和t可以使用下面的算法計(jì)算得到。該算法的輸入是整數(shù)a，b，輸出是整數(shù)sn， tn和rn，滿足sn·a+ tn·b= s·a+ t·b=rn=gcd（a，b）=（a，b），該算法的循環(huán)不變式是si·a+ ti·b=ri（i=1，2，…n），此循環(huán)不變式也是信息安全數(shù)學(xué)基礎(chǔ)中廣義歐幾里得除法的一個(gè)定理，因而是正確的。其計(jì)算過(guò)程如下表所示。計(jì)算時(shí)間復(fù)雜度是O（lg n），其中n是整數(shù)a，b中絕對(duì)值較大者。該算法主要用于求模n乘法逆元，在密碼學(xué)RSA算法等涉及求逆元的算法都會(huì)使用到該算法，是必須要掌握的一個(gè)算法。該算法計(jì)算過(guò)程代碼如下。[4]

3.模m原根計(jì)算算法

根據(jù)信息安全數(shù)學(xué)基礎(chǔ)中初等數(shù)論結(jié)論模m有原根的重要條件是m=2、4、pa、2pa，其中p是素?cái)?shù)。計(jì)算原根的關(guān)鍵是找到素?cái)?shù)p其中一個(gè)原根g，素?cái)?shù)p的其他原根可以通過(guò)計(jì)算gd的得到，這里的d是一個(gè)與p-1互素的正整數(shù)，即（d，p-1）=1。只要找到素?cái)?shù)p的一個(gè)原根，就可計(jì)算pa、2pa的原根，從而可以計(jì)算從有原根的任意模數(shù)m的原根。奇素?cái)?shù)p的原根計(jì)算算法是首先計(jì)算p-1的不同素因子q1，…，qs，g從小到大遍歷這s個(gè)素因子，若，則此素因子g就是素?cái)?shù)p的一個(gè)原根。該計(jì)算機(jī)算法計(jì)算工作量主要是p-1的素因子分解，當(dāng)p是非常大的素?cái)?shù)時(shí)，該計(jì)算機(jī)問(wèn)題NP問(wèn)題，計(jì)算機(jī)工作量是比較大的，但對(duì)一般意義的奇素?cái)?shù)p，這個(gè)計(jì)算算法還是可以接受的。[5]

本文探討了融合算法設(shè)計(jì)與分析思想到信息安全數(shù)學(xué)基礎(chǔ)教學(xué)中，一方面可以提高知識(shí)綜合應(yīng)用的能力，另一方面可以提高信息安全數(shù)學(xué)基礎(chǔ)教。

結(jié)語(yǔ)

本文探討了融合學(xué)的效果，提高了學(xué)生學(xué)習(xí)的積極性和主動(dòng)性。如何應(yīng)用算法設(shè)計(jì)與分析的思想設(shè)計(jì)更為有效的信息安全數(shù)學(xué)基礎(chǔ)中有關(guān)問(wèn)題的算法及更加有效地融合算法設(shè)計(jì)和信息安全數(shù)學(xué)基礎(chǔ)是下一步要考慮的問(wèn)題之一，其次需要利用微信等社交網(wǎng)絡(luò)工具和聊天機(jī)器人技術(shù)進(jìn)一步搭建信息安全數(shù)學(xué)基礎(chǔ)課程答疑服務(wù)系統(tǒng)也是下一步考慮的問(wèn)題之一。

參考文獻(xiàn)

[1]閆璽璽，劉琨.《信息安全數(shù)學(xué)基礎(chǔ)》教學(xué)方法探索與體會(huì)[J].考試周刊，2014（06）：114-115.

[2]李瑞琪，高敏芬，賈春福等.信息安全數(shù)學(xué)基礎(chǔ)的“講一練二考三”改革方案設(shè)計(jì)[J].計(jì)算機(jī)教育，2016（11）：27-29.

[3]秦艷琳，吳曉平.提高信息安全數(shù)學(xué)基礎(chǔ)課程教學(xué)效果的幾種途徑[J].計(jì)算機(jī)教育，2016（3）：132-135.

[4]陳恭亮.信息安全數(shù)學(xué)基礎(chǔ)（第二版）[M].清華大學(xué)出版社，2016.

[5]殷建平，徐云，王剛等譯.算法導(dǎo)論（第三版）[M].機(jī)械工業(yè)出版社，2014.

作者簡(jiǎn)介

楊文忠，（1971.7—），男，河南，博士研究生，副主任，副教授，信息安全博士，碩士生導(dǎo)師。研究方向?yàn)榫W(wǎng)絡(luò)空間內(nèi)容安全、算法設(shè)計(jì)與分析、無(wú)線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)路由等。已發(fā)表文章20多篇，主持和參與國(guó)家級(jí)和省部級(jí)項(xiàng)目10多項(xiàng)。