曹 浩 陳雪敏 董姍姍

安徽科技學院，安徽 鳳陽 233100

引言

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

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

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

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

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

1.1 模逆元的概念

定義1[7]設m 是一個正整數(shù)，a 是一個整數(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。

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

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

1.2 模逆元的求解方法

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

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

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

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

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

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

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

下面以一個具體的例子，說明擴展的歐幾里德算法的運行過程。

例1 設m＝79，a ＝27，利用擴展的歐幾里德算法計算a 的模m 逆元。

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

第1 輪:

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

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

第2 輪:

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

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

第3 輪:

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

第4 步:由輾轉相除過程: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))，化簡后得到1 ＝13m-38a，輸出s＝-38。

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

(2)歐拉定理

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

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

2 模逆元的求解技巧

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

定理1 設m 是一個大于1 的正整數(shù)，a 是一個非零整數(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 關于模m 互為逆元。

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

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

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

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

通過例1、例2 和例3 的解題過程，可以明顯地發(fā)現(xiàn)，利用我們提出的技巧，可以用更少的計算量，簡單方便地計算出a 的模m 逆元。 為進一步理解求模逆元的技巧，我們再給出兩個具體實例。

例4 設m＝79，a ＝7，顯然，a ＝7 既不是m-1＝78 的因子，也不是m＋1 ＝80 的因子，如何巧妙計算a 的模m 逆元呢? 事實上，在模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，進而由定理2得到a 的模m＝79 逆元為a-1＝(-8)-1×3-1×3-1(mod m)＝(-10)×(-26)×(-26)(mod 79)＝34。

例5 設m ＝41，a ＝22，對a 在模m ＝41 的意義下進行分解: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，進而由定理2 得到a 的模m ＝41 逆元為a-1＝2-1×(-5)-1×6-1(mod m)＝(-20)×8×7(mod 41)＝28。

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

3 結束語

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