信息安全实验三：求模逆算法 2019.04.18
实验三：求模逆算法
一、实验目的
理解、掌握求模逆算法的基本过程。
二、实验内容
- 熟悉扩展欧几里德算法。
- 利用扩展欧几里德算法求模逆，要求：任意输入两个整数a,m；输出a-1mod m;当模逆不存在时，输出出错提示。
三、求模逆算法基本原理
四、实验过程
1、使用扩展欧几里得算法的关键代码
套用公式即可
2、使用费马小定理的快速幂算法的关键代码
使用快速幂计算出即可
五、实验结果
分别输入 a和m计算出a模m的逆元
（左侧是欧几里得算法得到的结果，右侧是费马小定理计算出来的结果。）
费马小定理只能适用于m为质数的情况，适用范围比欧几里得算法小，是a和m互质的一种特殊情况。欧几里得算法只需要a和m互质就可以求出模逆。