【利用扩展Euclidean算法求乘法逆】
1. Equipment
（1） operating system version ：WIN 10
（2） CPU instruction set: x 64
（3） software ：Visual Studio 2019
2. process
- Problem background analysis
利用扩展Euclidean算法计算下列的乘法逆: (1)
mod 101 (2)
mod 1234 (3)计算 gcd(57,93)，并找出整数s和t，使得57s 93t=gcd(57,93) (4）求解下列同余方程组
采用扩展欧几里得算法求解乘法逆元，通过学习可知，扩展欧几里得算法除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数），即得到ax by=gcd(a,b)的整数解。若 a * x == 1mod p，则称x为a关于模p的乘法逆元。
- Solution
code：先分别编写所需的函数部分
代码语言：javascript复制#include<iostream>
using namespace std;
/*
* @Author:timerring
* @Date: 2021-11-19 12:41:32
* @LastEditTime: 2021-11-21 23:12:45
* @FilePath:c:UserstimerringEuclidean.cpp
*/
int exgcd(int a, int b, int& x, int& y) {
//定义扩展欧几里得算法
if (b == 0)
{//最里面ax 0=a的情况
x = 1;
y = 0;
return a;
}
//通过递归的方法进到最里层确定x，y的值，从逐步到外层计算出x，y
int d = exgcd(b, a % b, x, y);
//x==y1,y==x1-a/b*y1
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
int gcd(int a, int b) {
//定义欧几里得算法
if (a % b == 0) {
return b;
}
return gcd(b, a % b);
}
bool linearEquation(int a, int b, int c, int& x, int& y)
{//定义求解线性等式
int d = exgcd(a, b, x, y);
if (c % d) return false;
int k = c / d;
x *= k; y *= k;//求的只是其中一个解
return true;
}
int inverse(int a, int p) {
//定义求逆元的方法
int x, y, gcd;
gcd = exgcd(a, p, x, y);
if (gcd == 1) {
//确保x为正数
x = (x % p p) % p;
return x;
}
else {
cout << "a,p不互质";
return 0;
}
}运行结果：
1.对于（1）（2）题，可以直接采取调用inverse函数的方法求解其逆元：
代码语言：javascript复制int main() {
//求解ax py = gcd(a,p) = 1
int a, p;
cout << "请输入 a p" << endl;
cin >> a >> p;
cout << "a mod p的乘法逆元是" << inverse(a, p);
return 0;
}由结果可知，17mod101的逆元是6，357mod1234的逆元是1075.
2.对于（3）题，可以使用linearEquation函数完成对于线性等式a * s p * t = gcd（a，p）的求解。
代码语言：javascript复制int main() {
//求解ax py = gcd(a,p)
int a, p, x, y, temp;
cout << "请输入对应的a和p：" << endl;
cout << "（a * s p * t = gcd（a，p））" << endl;
cin >> a >> p;
temp = gcd(a, p);
linearEquation(a, p, temp, x, y);
cout << "对应的s和t是" << "ns = "<<x <<"nt = "<<y;
return 0;
}由结果可知，求解得s = -13，t = 8。
3.对于（4）题求解同余方程组，可以采用不断合并方程的方式完成求解。
代码语言：javascript复制int main()
{
int n, b1, m1;
bool tf = true;
printf("请输入方程组的个数：");
scanf("%lld", &n);
printf("请分别输入方程组的参数：n");
scanf("%lld%lld", &b1, &m1);
for (int u = 2; u <= n; u )
{
int b2, m2;
scanf("%lld%lld", &b2, &m2);
int A, B, x, y, dd = b2 - b1;
A = m1, B = m2;
int d = exgcd(A, B, x, y);
if (dd % d != 0) { printf("no solution!"); return 0; }
x = (x * (dd / d) % (B / d) (B / d)) % (B / d);
b1 = m1 * x b1;
m1 = m1 * m2 / d;
}
if (tf == false) printf("no solution!");
else printf("方程组的解为：%dn", b1);
return 0;
}由结果可知，同余方程组的解为14387，通过验算可知，结果正确。
3. summary and harvest
我对扩展欧几里得算法及其多种的应用更加熟练了，也让我对它的理解更加全面，例如对于ax mod p = 1，x就是a 在mod p乘法群的乘法逆元，通过拓展欧几里得算法，得到ax py = gcd（a，p），因为a属于模p乘法群，所以a<p，所以a与p互素，则有gcd(a,p)=1，即 ax py = 1。同时两边求mod p，即有 ax = 1（mod p），即此时的x就是乘法逆元，通过这种方法就可以求出其乘法逆元。
在写代码时，我通过递归的方法实现了欧几里得算法的编写，其实算法的实现原理就是，有两个整数a，b，每次一个数字r = a % b，然后把b放到a的位置，把r放到b的位置，递归调用实现。结束条件是当 a%b == 0的时候停止。受到编写欧几里得算法时的启发，我发现扩展欧几里得的算法或许可以通过递归的方式求解，大概在纸上写了基础逻辑之后，我就用C 通过递归的方法进到最里层确定x，y的值，从逐步到外层计算出x，y的值。
求解线性方程时，由于 ax by=c有解 => c=k*gcd(a,b)=kd，我们先考虑求解 ax by=d，由欧几里得算法,d=bx’ (a mod b)y’=bx’ (a-[a/b]b)y’=ay’ b(x’-[a/b])y’ ，则由上述式子，我们可以得出 x=y’ ,y=x’-[a/b]y’，即可得到这对解。
求解同余方程组时我是采用合并的方式实现的。例如我们观察两个同余方程
其实这个可以写成以下形式
两个式子相减可以得到
然后这里m1,m2,(a2−a1)都是已知的，所以可以当一个不定方程来解，这样的话就可以解出一个y1，带入原式就可以得到一个可能的x0，x0仅仅满足下面这个式子x=x0 k∗lcm(m1,m2) 这个又可以看成一个新的同余方程
然后如果满足这个方程就可以满足那两个方程了，就成功地将两个方程合为一个，一直合下去就可以得到一个唯一的不定方程，求解即可。
初学信息安全，可能存在错误之处，还请各位不吝赐教。
受于文本原因，本文相关算法实现工程无法展示出来，现已将资源上传，可自行点击下方链接下载。
扩展Euclidean算法求乘法逆原理详解与算法实现工程文件
