信息安全數(shù)學(xué)基礎(chǔ)教學(xué)中模逆元的求解技巧*

曹 浩 陳雪敏 董姍姍

安徽科技學(xué)院，安徽 鳳陽(yáng) 233100

引言

隨著信息技術(shù)的發(fā)展，越來(lái)越多的敏感數(shù)據(jù)需要在云端存儲(chǔ)并通過(guò)網(wǎng)絡(luò)來(lái)傳輸，確保敏感數(shù)據(jù)在存儲(chǔ)和傳輸?shù)倪^(guò)程中不被泄漏，對(duì)于維護(hù)國(guó)家網(wǎng)絡(luò)安全主權(quán)、保護(hù)政府和企業(yè)的機(jī)密以及個(gè)人用戶的隱私，均具有重要的現(xiàn)實(shí)意義。 信息安全技術(shù)可以對(duì)數(shù)據(jù)處理后再存儲(chǔ)和傳輸，使之不會(huì)被非法用戶竊取，對(duì)于保護(hù)數(shù)據(jù)安全起到至關(guān)重要的作用。 信息安全技術(shù)水平的高低歸根到底取決于信息安全人才隊(duì)伍的建設(shè)狀況。 因此，高度重視信息安全相關(guān)專業(yè)的建設(shè)，大力提升信息安全專業(yè)的人才培養(yǎng)質(zhì)量，以信息安全人才隊(duì)伍建設(shè)為驅(qū)動(dòng)，深入推進(jìn)信息安全產(chǎn)業(yè)的全面發(fā)展，對(duì)于維護(hù)國(guó)家安全和社會(huì)穩(wěn)定，具有重要的戰(zhàn)略意義。

《信息安全數(shù)學(xué)基礎(chǔ)》是信息安全本科專業(yè)的一門專業(yè)基礎(chǔ)課程，課程內(nèi)容主要由初等數(shù)論和抽象代數(shù)兩部分組成，介紹了信息安全專業(yè)學(xué)生所需掌握的整除、同余式、原根與指數(shù)、群、有限域等知識(shí)，是學(xué)習(xí)《現(xiàn)代密碼學(xué)》、《信息論與編碼理論》等后續(xù)專業(yè)核心課程的基本支撐。該課程具有理論性強(qiáng)、知識(shí)點(diǎn)散、內(nèi)容抽象、信息量大等特點(diǎn)，教學(xué)課時(shí)有限非常有限。 如何針對(duì)主要的知識(shí)點(diǎn)，合理地設(shè)計(jì)教學(xué)內(nèi)容和選擇教學(xué)方法，達(dá)到較好的教學(xué)效果，是擺在教師面前亟待解決的問(wèn)題。 秦艷琳等[1]采用案例教學(xué)法，將數(shù)學(xué)知識(shí)與密碼學(xué)案例相結(jié)合，充分體現(xiàn)啟發(fā)式教學(xué)理念，從而激發(fā)學(xué)生的學(xué)習(xí)興趣；朱潛[2]等將CDIO 教學(xué)理念引入到課程教學(xué)模式和實(shí)踐教學(xué)模式中，取得了較好的教學(xué)效果；巫玲[3]探索了任務(wù)型專題教學(xué)模式，提出重新配置教學(xué)內(nèi)容，以應(yīng)用為目標(biāo)、以應(yīng)用為動(dòng)力、以應(yīng)用為核心，通過(guò)設(shè)定具體的活動(dòng)任務(wù)，培養(yǎng)學(xué)生發(fā)現(xiàn)問(wèn)題和解決問(wèn)題的主動(dòng)性和創(chuàng)造力；李瑞琪[4]等利用“講一練二考三”的教學(xué)理念進(jìn)行教學(xué)改革；高瑩等[5]采用反例教學(xué)法，加深了學(xué)生對(duì)定理和命題的理解；周潔等[6]提出以密碼學(xué)中困難問(wèn)題為主線設(shè)計(jì)教學(xué)內(nèi)容，使課程內(nèi)容的具有較好的系統(tǒng)性。

模逆元是《信息安全數(shù)學(xué)基礎(chǔ)》課程中的一個(gè)核心概念，貫穿整個(gè)課程知識(shí)體系的始終，在RSA、AES、Diffie-Hellman、ElGamal 等諸多知名的密碼體制和密碼協(xié)議中均有重要的應(yīng)用。 因此，熟練掌握模逆元的概念及求解方法，是使學(xué)生準(zhǔn)確把握《信息安全數(shù)學(xué)基礎(chǔ)》課程體系的重中之重。 當(dāng)前，求解模逆元的普適性方法是擴(kuò)展地歐幾里德算法和歐拉定理，幾乎沒(méi)有其它有效的方法。 在教學(xué)過(guò)程中，僅僅使用這兩種方法求解模逆元，學(xué)生無(wú)法深入理解模逆元的內(nèi)涵，對(duì)模逆元求解技巧進(jìn)行探索性研究并幫助學(xué)生快速理解模逆元的內(nèi)涵和性質(zhì)，從而達(dá)到理想的教學(xué)效果，是非常有意義的事情。

本文對(duì)模逆元的兩種主要求解方法進(jìn)行了總結(jié)，并探索了適合教學(xué)過(guò)程中使用的模逆元求解的其他技巧。 通過(guò)這些技巧，可以加深學(xué)生對(duì)模逆元的概念和求解方法的理解，對(duì)提高整個(gè)課程的教學(xué)質(zhì)量，具有重要的實(shí)踐意義。

1 模逆元的概念及求解方法

1.1 模逆元的概念

定義1[7]設(shè)m 是一個(gè)正整數(shù)，a 是一個(gè)整數(shù)，如果存在整數(shù)a′，使得a a′≡1(mod m)成立，則a 叫做模m 的可逆元，a′叫做a 的模m逆元。

一般地，正整數(shù)m 是大于1 的整數(shù)，整數(shù)a存在模m 逆元的充要條件是a 與m 互素。 通常將a 的模m 逆元記做a-1(mod m)，在不引起混淆的情況下，也可以直接記做a-1。

模逆元的概念貫穿于整個(gè)課程體系的始終，如同余式ax≡1(mod m)的求解相當(dāng)于同余式兩邊同時(shí)乘以a 的模m 逆元，仿射密碼和Hill 密碼的加解密過(guò)程均需多次使用模逆運(yùn)算，運(yùn)用中國(guó)剩余定理求解同余方程組需要多次模逆元求解、RSA 公鑰密碼系統(tǒng)的加解密和Diffie-Hellman 密鑰協(xié)商也需要多次模逆運(yùn)算等。 因此，模逆元的求解是《信息安全數(shù)學(xué)基礎(chǔ)》課程中的一個(gè)核心概念。

需要注意的是，如果a-1是a 的模m 逆元，那么a 也是a-1的模m 逆元，此時(shí)也稱a 和a-1模m 互逆。 此外，a-1和a 模m 互逆的充要條件是:對(duì)任意的兩個(gè)整數(shù)k 和k′，km＋a 和k′m＋a-1模m 互逆的。 因此，a 的模m 逆元a-1并不是唯一的，為模m 剩余類[a-1]中的任意一個(gè)代表元，它們恰好組成以a-1為代表元的模m 的剩余類[a-1]，即a 的模m 逆元在模m 同余的意義下是唯一的。 為方便起見(jiàn)，在不會(huì)引起混淆的情況下，本文認(rèn)為模m 的剩余類[a-1]中的元素均是相同的，即在模m 同余的意義下a-1＝k′m＋a-1。

1.2 模逆元的求解方法

在諸多《信息安全數(shù)學(xué)基礎(chǔ)》教材中，求解模逆元的方法主要有兩種:擴(kuò)展的歐幾里德算法和歐拉定理。

(1)擴(kuò)展的歐幾里德算法

設(shè)m 是一個(gè)大于1 的正整數(shù)，a 是一個(gè)與m互素的整數(shù)，根據(jù)擴(kuò)展的歐幾里德算法，反復(fù)使用輾轉(zhuǎn)相除法并反演推導(dǎo)，可以找到兩個(gè)整數(shù)s和t，滿足:sa＋mt＝1，即sa ≡1(mod m)，s 就是a的模m 逆元。 擴(kuò)展的歐幾里德算法可描述如下:

第1 步:以m 為被除數(shù)和a 為除數(shù)做輾轉(zhuǎn)相除法。

第2 步:判斷余數(shù)是否為1，如果是，轉(zhuǎn)到第4 步；否則，轉(zhuǎn)到第3 步。

第3 步:將除數(shù)作為被除數(shù)，余數(shù)作為除數(shù)，進(jìn)行輾轉(zhuǎn)相除后，轉(zhuǎn)到第2 步。

第4 步:將前面的輾轉(zhuǎn)相除過(guò)程進(jìn)行反演推導(dǎo)，找到兩個(gè)整數(shù)s 和t，滿足:sa＋mt ＝1，并輸出a 的模m 逆元s。

下面以一個(gè)具體的例子，說(shuō)明擴(kuò)展的歐幾里德算法的運(yùn)行過(guò)程。

例1 設(shè)m＝79，a ＝27，利用擴(kuò)展的歐幾里德算法計(jì)算a 的模m 逆元。

第1 步:m ＝79，a ＝27:m ＝2a＋r1(這里r1＝25)。

第1 輪:

第2 步:余數(shù)r1＝25≠1，轉(zhuǎn)第3 步。

第3 步:a ＝27，r1＝25:a ＝1r1＋r2(這里r2＝2)，轉(zhuǎn)第2 步。

第2 輪:

第2 步:余數(shù)r2＝2≠1，轉(zhuǎn)第3 步。

第3 步:r1＝25，r2＝2:r1＝12r2＋r3(這里r3＝1)，轉(zhuǎn)第2 步。

第3 輪:

第2 步:余數(shù)r3＝1，轉(zhuǎn)第4 步。

第4 步:由輾轉(zhuǎn)相除過(guò)程:m ＝2a＋r1，a ＝1r1＋r2，r1＝12r2＋r3得到r1＝m-2a，r2＝a -r1，1 ＝r3＝r1-12r2；從而可得1 ＝r1-12r2＝r1- 12(a -r1)＝(m-2a)-12(a-(m-2a))，化簡(jiǎn)后得到1 ＝13m-38a，輸出s＝-38。

因此，27 的模79 逆元為-38 ＝41。

(2)歐拉定理

設(shè)m 是一個(gè)大于1 的正整數(shù)，a 是一個(gè)與m互素的整數(shù)，根據(jù)歐拉定理得aφ(m)≡1(mod m)(其中φ(m)表示小于m 的非負(fù)整數(shù)中與m 互素的整數(shù)個(gè)數(shù)，稱為歐拉函數(shù))，所以a 的模m逆元為aφ(m)-1。

例2 對(duì)于例1 中的m ＝79，a ＝27，a 的模m逆元可以利用歐拉定理直接計(jì)算得:a′＝aφ(m)-1＝2777(mod 79)＝27·274·278·2764(mod 79)＝27·8·64·38(mod 79)＝41。

2 模逆元的求解技巧

擴(kuò)展的歐幾里德算法是求解模逆元的有效算法，特別地，當(dāng)m 和a 均是大整數(shù)時(shí)，該算法非常奏效；歐拉定理直接給出求模逆元的公式，計(jì)算過(guò)程直觀。 以上兩種方法均適合讓學(xué)生通過(guò)編程來(lái)實(shí)現(xiàn)。 然而，在具體的教學(xué)過(guò)程和習(xí)題求解中，遇到的模整數(shù)m 大多都比較小，利用擴(kuò)展的歐幾里德算法求解模逆元需要多次輾轉(zhuǎn)相除和反演運(yùn)算，利用歐拉定理求解模逆元需要模指數(shù)運(yùn)算，兩種方法的計(jì)算量均較大，耗費(fèi)時(shí)間較長(zhǎng)。 當(dāng)模整數(shù)m 較小時(shí)，比如100 以內(nèi)的整數(shù)，教會(huì)學(xué)生如何快速地求解模逆元，對(duì)加深學(xué)生對(duì)模運(yùn)算和模逆元的理解，具有重要的指導(dǎo)意義。 基于此，我們探索一種適用于日常教學(xué)和習(xí)題練習(xí)中的快速求解模逆元的技巧。 為了方便討論，我們給出關(guān)于模逆元的兩個(gè)重要性質(zhì)。

定理1 設(shè)m 是一個(gè)大于1 的正整數(shù)，a 是一個(gè)非零整數(shù)。 那么以下命題成立:

(i) 如果a 是整數(shù)km＋1 的因子，那么a 存在模m 逆元，且a 的模m 逆元為a-1＝(km ＋1)/a。

(ii) 如果a 是整數(shù)km-1 的因子，那么a 存在模m 逆元，且a 的模m 逆元為a-1＝-(km-1)/a。

證明:(i) 如果a 是整數(shù)km＋1 的因子，那么a·(km＋1)/a ＝km＋1≡1(mod m)，所以b 與(km＋1)/a 關(guān)于模m 互為逆元。

(ii) 如果a 是整數(shù)km-1 的因子，那么a·[-(km-1)/a]＝1-km≡1(mod m)，所以a 與-(km-1)/a 關(guān)于模m 互為逆元。

定理2 設(shè)m 是一個(gè)大于1 的正整數(shù)，a ＝a1a2是一個(gè)與m 互素的整數(shù)，則a 的模m 逆元為a-1＝a1-1a2-1。

依據(jù)定理1 和定理2，我們?cè)诮虒W(xué)舉例中，將整數(shù)a 分解為若干個(gè)因數(shù)的乘積，如果每個(gè)因數(shù)都是整數(shù)km＋1 的因子，那么這些因數(shù)的模m逆元可以由定理1 直接給出，且a 的模m 逆元可以直接由這些因數(shù)的模m 逆元的乘積得到，大大簡(jiǎn)化了計(jì)算的工作量。

例3 對(duì)于例1 中的m ＝79，a ＝27，將a 分解為a ＝27 ＝3×3×3，由于3 是m-1 ＝78 的因子，由定理1 得到3 的模m 逆元為3-1＝-78/3 ＝-26，進(jìn)而由定理2 得到a 的模m 逆元為a-1＝3-1×3-1×3-1(mod m)＝(-26)×(-26)×(-26)(mod 79)＝41。

通過(guò)例1、例2 和例3 的解題過(guò)程，可以明顯地發(fā)現(xiàn)，利用我們提出的技巧，可以用更少的計(jì)算量，簡(jiǎn)單方便地計(jì)算出a 的模m 逆元。 為進(jìn)一步理解求模逆元的技巧，我們?cè)俳o出兩個(gè)具體實(shí)例。

例4 設(shè)m＝79，a ＝7，顯然，a ＝7 既不是m-1＝78 的因子，也不是m＋1 ＝80 的因子，如何巧妙計(jì)算a 的模m 逆元呢? 事實(shí)上，在模m ＝79 的意義下，a ＝7 ＝7-79 ＝-72 ＝-8×3×3，-8 是m＋1＝80 的因子，3 是m-1 ＝78 的因子，由定理1 得到-8 和3 的模m ＝79 逆元分別為(-8)-1＝80/(-8)＝-10 和3-1＝-78/3 ＝-26，進(jìn)而由定理2得到a 的模m＝79 逆元為a-1＝(-8)-1×3-1×3-1(mod m)＝(-10)×(-26)×(-26)(mod 79)＝34。

例5 設(shè)m ＝41，a ＝22，對(duì)a 在模m ＝41 的意義下進(jìn)行分解:a ＝22 ＝2×11 ＝2×(11-41)＝2×(-30)＝2×(-5)×6，2 和-5 是是m-1 ＝40的因子，6 是m＋1 ＝42 的因子，由定理1 可得2、-5、6 的模m ＝41 逆元分別為2-1＝-40/2 ＝-20、(-5)-1＝-40/(-5)＝8 和6-1＝42/6 ＝7，進(jìn)而由定理2 得到a 的模m ＝41 逆元為a-1＝2-1×(-5)-1×6-1(mod m)＝(-20)×8×7(mod 41)＝28。

通過(guò)例4 和例5 的解題過(guò)程發(fā)現(xiàn)，對(duì)于不能直接利用解題技巧求解模逆元的題目，可以在模m 同余的意義下對(duì)a 及其因子進(jìn)行變換和分解后，再利用解題技巧進(jìn)行模逆元求解。

3 結(jié)束語(yǔ)

模逆元的概念貫穿《信息安全數(shù)學(xué)基礎(chǔ)》整個(gè)課程知識(shí)體系的始終，是學(xué)好該課程的前提和基礎(chǔ)。 本文在對(duì)模逆元的求解方法總結(jié)的基礎(chǔ)上，探索了適合實(shí)際教學(xué)的求解模逆元的技巧和方法。 本人在具體的教學(xué)過(guò)程中，首先利用擴(kuò)展的歐幾里德算法和歐拉定理，對(duì)模逆元的求解方法進(jìn)行講解清楚并輔以例題和習(xí)題，使學(xué)生對(duì)模逆元的概念及其求解方法有了一定的理解，然后，通過(guò)具體的例題，引導(dǎo)學(xué)生使用解題技巧進(jìn)行模逆元的求解，不僅加深了學(xué)生對(duì)模運(yùn)算的理解，更加深了學(xué)生對(duì)模逆元的理解，學(xué)生在技巧的使用中充分發(fā)揮自己的想象力，在模m 同余的意義下對(duì)a 做不同的分解，從而找到不同的求解模逆元的方法，激發(fā)了學(xué)生的學(xué)習(xí)興趣和創(chuàng)新能力，取得了較好的教學(xué)效果。