上一篇fermat素性检测算法的文章请跳转到： https://blog.csdn.net/Koz_0/article/details/109177491
基础知识上课老师都讲了，也有相关的ppt，这里就不多说了。 但是我个人觉得这个逆元的概念比较有趣。 其基本思想和解方程组差不多，但这里是同余方程组。
visio流程图如下图所示：
使用的是vc 6++ 和miracl大整数库。 miracl整数库的配置可以自行去百度一下，应该也有不少。我这里提供一下miracl整数库的配置资源吧。见链接： 如果在配置的时候有什么问题可以私信或者评论，我会尽力而为的。 链接：http@@s://p@@an.baidu.c@@om/s/1HKP-v0OFQIPyZmMjRSPFJw 提取码：jops （把@删除掉就是完整链接）
此部分主要列举了一些用到的函数，因为是大整数，所以对于一般的“=”赋值或者“*”乘法都无法实现，需要用函数实现。
1、 miracl *mip = mirsys(10000,10); //初始化10的五次方 mip->IOBASE = 10; //设置 10进制 2、 x = mirvar(0); //初始化 //给x赋值大整数0 3、 cinnum(m,fp);//从文件中读取一个数 4、 bigrand(x,a);//生成随机数 //a<x=m-1 5、 egcd(a,m,g);//求a和m的最大公约数 //g = (a,m) 6、 powmod(a,x,m,r);//模幂运算， //r=ax (mod m) 7、 cotnum(m,stdout)//把大整数m打印到终端 8、 multiply(mj[i],m, m); //m = m * mi 9、 divide(x, y, z) //z = x / y //也可以求模值 divide(x,y,z) //x = x mod y 10、 xgcd(Mj[i], mj[i], Mj_contrary[i], Mj_contrary[i], Mj_contrary[i]); //计算mj的逆 xgcd(x,p,z,z,z); //z = x^-1 mod p => z*x = 1 (mod p)这里就不多说什么了，算法比较简单，难点是其中库函数的运用。 代码中也有注释，不懂的可以私信我。 P.S.我的代码里面那块注释我也没有什么好方法来实现，如果有大佬有什么好方法希望能指明方向。 代码如下：
#include<stdio.h> #include<math.h> #include"miracl.h" int main() { int j = 0; int i = 0; FILE *fd; int k = 3; miracl *mip = mirsys(1000, 10);//初始化10的五次方 //mip->IOBASE = 10; //设置 10进制 big a[3], mj[3], Mj[3], Mj_contrary[3]; big m, res; big temp, one; big nok; m = mirvar(1); one = mirvar(1); res = mirvar(0); temp = mirvar(0); nok = mirvar(1); for (i=0;i<k;i++) { a[i] = mirvar(0); mj[i] = mirvar(0); Mj[i] = mirvar(0); Mj_contrary[i] = mirvar(0); } fd = fopen("2.txt","r"); if(fd == NULL) { printf("Error!"); return 0; } for (i=0;i<k;i++) { cinnum(a[i],fd); } for (i=0;i<k;i++) { cinnum(mj[i],fd); } fclose(fd); for (i=0;i<k;i++){ //判断mi是否是互素的≡ for (j=i+1;j<k;j++) { egcd(mj[i], mj[j], temp); if (compare(one, temp)) { printf("mj不互素"); return 0; } } } /*没有办法把cotnum自带的换行取消掉，没法打印出来方程组 printf("同余方程组为：\n"); for(i=0;i<k;i++){ printf(" x≡ "); cotnum(a[i], stdout); printf(" ( mod "); cotnum(mj[i],stdout); printf(" )"); printf("\n"); } printf("\n"); */ for (i=0;i<k;i++){//m = m1*m2*m3 multiply(mj[i],m, m);//m = m * mi } for (i=0;i<k;i++) { copy(m, temp);// temp = m divide(temp, mj[i], Mj[i]);//求Mj = m / mj //divide(x, y, z) z = x / y //这里不能直接用m，因为divide也有取余的功能，会改变m的值 } for (i=0;i<k;i++){ xgcd(Mj[i], mj[i], Mj_contrary[i], Mj_contrary[i], Mj_contrary[i]);//计算mj的逆 //xgcd(x,p,z,z,z); z = x^-1 mod p => z*x = 1 (mod p) } for (i=0;i<k;i++) { multiply(Mj[i], Mj_contrary[i], Mj[i]); multiply(Mj[i], a[i], temp); divide(temp, m, nok); //求temp (mod m) //divide(x,y,z) =>x = x mod y add(res, temp, res); } divide(res, m, temp); printf("得到方程组的解为：\n"); printf("x = "); cotnum(res, stdout); mirkill(m); //释放内存 mirkill(one); mirkill(res); mirkill(m); mirkill(temp); /*好像加上不知道为什么会报错，就不加了，对结果无影响 mirkill(a[3]); mirkill(mj[3]); mirkill(Mj[3]); mirkill(Mj_contrary[3]); */ mirexit(); //清除MIRACL系统，释放所有的内部变量 getchar(); return 0; }这个是此课程的第二个实验。下一个实验我也会尽快上传的。
