MFIS-Lab3：实现中国剩余定理
信息安全数学基础
课程实验报告
实验报告（三）
系 别： 网络空间安全系
班 级： secret!
姓 名： secret!
学 号： secret!
实验时间： 2023年10月30日
指导老师： secret!
- 实验内容
- 实验目标
理解中国剩余定理，用c++实现并不能调用现有库函数，并在优化时增加初始判断条件
- 实验原理
- 实验设计
实验共分为1个主函数和2个自定义函数。其中，主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出，chineseRemainder函数是实现中国剩余定理算法核心部分，extEuclidean函数是实现广义欧几里算法用来求解逆元。
- 定义变量和函数
主函数：
数组大小：n
存放模的数组：m[]
存放余数的数组：b[]
广义欧几里得系数：s，t
最大公因数：d
chineseRemainder函数：
最终结果：result
所有模的乘积：M
广义欧几里得系数：x，y
中国剩余定理的M：Mi
extEuclidean函数：
函数参数传入的余数：a
函数参数传入的模：b
广义欧几里得系数：x，y
最大公因数：d
- 主函数
主函数负责部分基本变量定义、判断中国剩余定理判断条件以及输入和输出
首先定义数组大小n，存放模的数组m，存放余数的数组b，尽量开大一些；
然后输入数组大小n，循环读入模m的元素，循环读入余数b的元素；
判断输入的模是否互素，通过双重for循环遍历模m数组，调用广义欧几里得函数extEuclidean的返回值最大公因数d判断，若存在两两不互素即最大公因数d不为1，则输出错误信息并直接返回程序；
若满足模两两互素，则调用中国剩余定理chineseRemainder函数并输出结果。
- chineseRemainder函数
函数是实现中国剩余定理算法核心部分
函数参数传入数组大小n，存放模的数组m，存放余数的数组b；
初始化结果result为0，所有模乘积M为1，定义用于广义欧几里得计算的系数x、y；
循环累乘计算出所有模乘积M，方便后续计算中国剩余定理中的Mi
循环逐个计算每一个同余式的结果并累加到最终结果result，Mi计算为所有模乘积M除以当前模m[i]，调用extEuclidean函数利用广义欧几里得求解模m[i]的逆元，得到系数x就是逆元，再利用中国剩余定理累乘b*Mi*x，此时及时对M取模使得结果不会太大超出范围；
将result+模M再取模M 的处理是保证结果result总为正数，理由是在广义欧几里得算出的逆元x没有取正数处理，所以求出的逆元可能是一个负数；
返回最终结果result。
- extEuclidean函数
函数是实现广义欧几里算法用来求解逆元
利用递归的思想迭代求解广义欧几里得系数x和y，递归出口是余数b为0；
接受两个参数 a 和 b，表示要计算的两个整数。还接受两个引用参数 x 和 y，用于返回计算结果。
首先检查 b 是否为0。如果是0，说明 a 是最大公约数，此时将 x 设置为1，y 设置为0，并直接返回。
如果 b 不为0，那么函数会递归调用自身，传入参数 b 和 a 除以 b 的余数 a % b，并接收返回的结果 x和 y。
通过递归调用，函数计算出最大公约数d，并将它们存储在传入的引用参数 x 和 y 中，函数迭代y的值并返回最大公因数d
- 实验结果
- 物不知数
题目：
输入解释：
依次输入：n=3；模m数组：3，5，7；余数b数组：2，3，2
输出结果：
23，与教材结果一致，表示最少有这么多物品
- 韩信点兵之二
题目：
输入解释：
依次输入：n=4；模m数组：5，6，7，11；余数b数组：1，5，4，10
输出结果：
2111人，与教材结果一致，表示最少有这么多兵
- 作业8
题目：
输入解释：
依次输入：n=5；模m数组：2，3，5，7，11；余数b数组：1，1，1，1，0
输出结果：
2101，经验算：2101/11=191，2101-1=2*3*5*7*10，即2|2101-1，3|2101-1，5|2101-1，7|2101-1
- 模不互素的情况
设计最后一个模数只与倒数第二个模数不互素，这样双重for循环判断模是否互素会遍历模m的所有元素，时间是n(n+1)/2。虽然调用extEuclidean函数使用递归实现，但程序反应很快看不出延时
输入解释：
依次输入：n=15；模m数组：99，100，101，97，89，79，73，47，43，23，29，17，19，13，169；余数b数组：15，14，13，12，11，10，9，8，7，6，5，4，3，2，1
输出结果：
模不互素：13和169的最大公因数是13
打印错误信息，表示模之间存在两两不互素情况，没有严格遵守中国剩余定理的使用条件，直接退出程序
六、总结
本次实验在不调用库函数的情况下用c++实现中国剩余定理，利用到实验一中的广义欧几里得算法求解最大公因数判断互素条件以及求解逆元，解决一次同余方程组的求解问题。