信息安全数学基础教学中模逆元的求解技巧*

曹 浩 陈雪敏 董姗姗

安徽科技学院，安徽 凤阳 233100

引言

随着信息技术的发展，越来越多的敏感数据需要在云端存储并通过网络来传输，确保敏感数据在存储和传输的过程中不被泄漏，对于维护国家网络安全主权、保护政府和企业的机密以及个人用户的隐私，均具有重要的现实意义。 信息安全技术可以对数据处理后再存储和传输，使之不会被非法用户窃取，对于保护数据安全起到至关重要的作用。 信息安全技术水平的高低归根到底取决于信息安全人才队伍的建设状况。 因此，高度重视信息安全相关专业的建设，大力提升信息安全专业的人才培养质量，以信息安全人才队伍建设为驱动，深入推进信息安全产业的全面发展，对于维护国家安全和社会稳定，具有重要的战略意义。

《信息安全数学基础》是信息安全本科专业的一门专业基础课程，课程内容主要由初等数论和抽象代数两部分组成，介绍了信息安全专业学生所需掌握的整除、同余式、原根与指数、群、有限域等知识，是学习《现代密码学》、《信息论与编码理论》等后续专业核心课程的基本支撑。该课程具有理论性强、知识点散、内容抽象、信息量大等特点，教学课时有限非常有限。 如何针对主要的知识点，合理地设计教学内容和选择教学方法，达到较好的教学效果，是摆在教师面前亟待解决的问题。 秦艳琳等[1]采用案例教学法，将数学知识与密码学案例相结合，充分体现启发式教学理念，从而激发学生的学习兴趣；朱潜[2]等将CDIO 教学理念引入到课程教学模式和实践教学模式中，取得了较好的教学效果；巫玲[3]探索了任务型专题教学模式，提出重新配置教学内容，以应用为目标、以应用为动力、以应用为核心，通过设定具体的活动任务，培养学生发现问题和解决问题的主动性和创造力；李瑞琪[4]等利用“讲一练二考三”的教学理念进行教学改革；高莹等[5]采用反例教学法，加深了学生对定理和命题的理解；周洁等[6]提出以密码学中困难问题为主线设计教学内容，使课程内容的具有较好的系统性。

模逆元是《信息安全数学基础》课程中的一个核心概念，贯穿整个课程知识体系的始终，在RSA、AES、Diffie-Hellman、ElGamal 等诸多知名的密码体制和密码协议中均有重要的应用。 因此，熟练掌握模逆元的概念及求解方法，是使学生准确把握《信息安全数学基础》课程体系的重中之重。 当前，求解模逆元的普适性方法是扩展地欧几里德算法和欧拉定理，几乎没有其它有效的方法。 在教学过程中，仅仅使用这两种方法求解模逆元，学生无法深入理解模逆元的内涵，对模逆元求解技巧进行探索性研究并帮助学生快速理解模逆元的内涵和性质，从而达到理想的教学效果，是非常有意义的事情。

本文对模逆元的两种主要求解方法进行了总结，并探索了适合教学过程中使用的模逆元求解的其他技巧。 通过这些技巧，可以加深学生对模逆元的概念和求解方法的理解，对提高整个课程的教学质量，具有重要的实践意义。

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

1.1 模逆元的概念

定义1[7]设m 是一个正整数，a 是一个整数，如果存在整数a′，使得a a′≡1(mod m)成立，则a 叫做模m 的可逆元，a′叫做a 的模m逆元。

一般地，正整数m 是大于1 的整数，整数a存在模m 逆元的充要条件是a 与m 互素。 通常将a 的模m 逆元记做a-1(mod m)，在不引起混淆的情况下，也可以直接记做a-1。

模逆元的概念贯穿于整个课程体系的始终，如同余式ax≡1(mod m)的求解相当于同余式两边同时乘以a 的模m 逆元，仿射密码和Hill 密码的加解密过程均需多次使用模逆运算，运用中国剩余定理求解同余方程组需要多次模逆元求解、RSA 公钥密码系统的加解密和Diffie-Hellman 密钥协商也需要多次模逆运算等。 因此，模逆元的求解是《信息安全数学基础》课程中的一个核心概念。

需要注意的是，如果a-1是a 的模m 逆元，那么a 也是a-1的模m 逆元，此时也称a 和a-1模m 互逆。 此外，a-1和a 模m 互逆的充要条件是:对任意的两个整数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 模逆元的求解方法

在诸多《信息安全数学基础》教材中，求解模逆元的方法主要有两种:扩展的欧几里德算法和欧拉定理。

(1)扩展的欧几里德算法

设m 是一个大于1 的正整数，a 是一个与m互素的整数，根据扩展的欧几里德算法，反复使用辗转相除法并反演推导，可以找到两个整数s和t，满足:sa＋mt＝1，即sa ≡1(mod m)，s 就是a的模m 逆元。 扩展的欧几里德算法可描述如下:

第1 步:以m 为被除数和a 为除数做辗转相除法。

第2 步:判断余数是否为1，如果是，转到第4 步；否则，转到第3 步。

第3 步:将除数作为被除数，余数作为除数，进行辗转相除后，转到第2 步。

第4 步:将前面的辗转相除过程进行反演推导，找到两个整数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 步:余数r1＝25≠1，转第3 步。

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

第2 轮:

第2 步:余数r2＝2≠1，转第3 步。

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

第3 轮:

第2 步:余数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 的正整数，a 是一个与m互素的整数，根据欧拉定理得aφ(m)≡1(mod m)(其中φ(m)表示小于m 的非负整数中与m 互素的整数个数，称为欧拉函数)，所以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 均是大整数时，该算法非常奏效；欧拉定理直接给出求模逆元的公式，计算过程直观。 以上两种方法均适合让学生通过编程来实现。 然而，在具体的教学过程和习题求解中，遇到的模整数m 大多都比较小，利用扩展的欧几里德算法求解模逆元需要多次辗转相除和反演运算，利用欧拉定理求解模逆元需要模指数运算，两种方法的计算量均较大，耗费时间较长。 当模整数m 较小时，比如100 以内的整数，教会学生如何快速地求解模逆元，对加深学生对模运算和模逆元的理解，具有重要的指导意义。 基于此，我们探索一种适用于日常教学和习题练习中的快速求解模逆元的技巧。 为了方便讨论，我们给出关于模逆元的两个重要性质。

定理1 设m 是一个大于1 的正整数，a 是一个非零整数。 那么以下命题成立:

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

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

证明:(i) 如果a 是整数km＋1 的因子，那么a·(km＋1)/a ＝km＋1≡1(mod m)，所以b 与(km＋1)/a 关于模m 互为逆元。

(ii) 如果a 是整数km-1 的因子，那么a·[-(km-1)/a]＝1-km≡1(mod m)，所以a 与-(km-1)/a 关于模m 互为逆元。

定理2 设m 是一个大于1 的正整数，a ＝a1a2是一个与m 互素的整数，则a 的模m 逆元为a-1＝a1-1a2-1。

依据定理1 和定理2，我们在教学举例中，将整数a 分解为若干个因数的乘积，如果每个因数都是整数km＋1 的因子，那么这些因数的模m逆元可以由定理1 直接给出，且a 的模m 逆元可以直接由这些因数的模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 的解题过程，可以明显地发现，利用我们提出的技巧，可以用更少的计算量，简单方便地计算出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 的解题过程发现，对于不能直接利用解题技巧求解模逆元的题目，可以在模m 同余的意义下对a 及其因子进行变换和分解后，再利用解题技巧进行模逆元求解。

3 结束语

模逆元的概念贯穿《信息安全数学基础》整个课程知识体系的始终，是学好该课程的前提和基础。 本文在对模逆元的求解方法总结的基础上，探索了适合实际教学的求解模逆元的技巧和方法。 本人在具体的教学过程中，首先利用扩展的欧几里德算法和欧拉定理，对模逆元的求解方法进行讲解清楚并辅以例题和习题，使学生对模逆元的概念及其求解方法有了一定的理解，然后，通过具体的例题，引导学生使用解题技巧进行模逆元的求解，不仅加深了学生对模运算的理解，更加深了学生对模逆元的理解，学生在技巧的使用中充分发挥自己的想象力，在模m 同余的意义下对a 做不同的分解，从而找到不同的求解模逆元的方法，激发了学生的学习兴趣和创新能力，取得了较好的教学效果。