MFIS-Lab1：求逆元和欧拉函数值
信息安全数学基础
课程实验报告
实验报告（一）
系 别： 网络空间安全系
班 级： secret!
姓 名： secret!
学 号： secret!
实验时间： 2023年10月17日
指导老师： secret!
- 实验内容
- 实验目标
理解求逆元和欧拉函数原理以及证明，并利用c++代码实现，并在基础上优化
- 实验原理
3.1 求逆元
根据教材内容证明过程可知，求解逆元有两种方法：
方法一：定义a*a’%m=1
方法二：广义欧几里得除法s*a+t*m=1,a’=s
3.2 求欧拉函数
结合欧拉函数定义和求解公式可知，求解过程如下：
遍历小于n的素数，减去能整除这些素数的个数，遍历完毕如果还是素数则进一步减去自身的倍数，剩下的个数是欧拉函数
- 实验设计
4.1求逆元
4.1.1方法一：定义
4.1.1.1 代码思路
（1）首先，从标准输入中读取两个整数a和m。
（2）定义一个变量inv_a，并初始化为-1。这个变量用来存储逆元。
（3）使用一个for循环，从1到m-1遍历所有可能的逆元。
（4）在循环中，通过判断(a * i) % m == 1来找到逆元。如果找到了逆元，将其赋值给inv_a，并使用break语句跳出循环。
（5）最后，将逆元inv_a输出到标准输出。
这段代码的时间复杂度为O(m)，因为需要遍历所有可能的逆元，适合m较小时遍历求解。
4.1.2 方法二：
4.1.2.1 代码思路
使用了扩展欧几里得算法来计算两个整数的逆元：
（1）定义了一个函数exgcd，用于计算a和b的最大公约数，并且通过引用参数x和y返回扩展欧几里得算法的结果。
在exgcd函数中，首先判断b是否为0，如果是，则将x设置为1，y设置为0，并返回a作为最大公约数。a*x+b*y=a
如果b不为0，则递归调用exgcd函数，将b和a%b作为参数，并将y和x的值交换，以便在递归返回时正确计算x和y的值。
在递归返回后，通过以下公式计算x和y的值：y -= a/b * x;
最后，exgcd函数返回最大公约数d。
（2）在main函数中，首先从输入中读取两个整数a和m。
然后定义了两个变量x和y，用于存储逆元的计算结果。
调用exgcd函数，将a和m作为参数，并将计算结果存储在x和y中。
接下来，通过判断最大公约数d是否等于1来确定是否存在逆元。如果d不等于1，则输出”没有逆元”。
如果d等于1，则计算逆元的值，并使用取模运算确保结果在范围(0, m)内，然后输出结果(x%m+m)%x，因为x就是逆元，但是这样处理保证数值为正
4.1.2.2 x和y是什么
在这段代码中，x和y是exgcd函数的参数，它们是用来存储扩展欧几里得算法计算过程中的中间结果。
具体来说，x和y分别表示方程ax + by = d中的未知数。在扩展欧几里得算法中，我们通过递归的方式计算最大公约数d，并且在计算过程中更新x和y的值。
在函数的开始，我们将x和y的初始值设为1和0，这是因为当b等于0时，方程变为ax + 0y = a，所以x的系数为1，y的系数为0。
然后，在递归调用中，我们将y赋值给x，将a % b赋值给y，并且通过递归计算最大公约数d。最后，我们通过y -= a / b * x来更新y的值，以便在递归返回时得到正确的结果。
因此，x和y在这段代码中起到了存储中间结果的作用，用于计算最大公约数和更新系数的值。
举一个例子：
当我们使用扩展欧几里得算法来计算两个数的最大公约数时，我们需要通过递归调用来更新变量 x 和 y 的值。交换 x 和 y 的位置是为了确保在递归返回时得到正确的结果。
假设我们要计算 a = 30 和 b = 18 的最大公约数，并找到满足方程 ax + by = d 的整数解。
首先，我们进行第一次递归调用 exgcd(b, a % b, y, x)，其中 b = 18，a % b = 12。我们将 y 和 x 的引用传递给递归调用。
在递归调用中，我们再次进行递归调用 exgcd(b, a % b, y, x)，其中 b = 12，a % b = 6。这一次，我们将 y 和 x 的引用传递给递归调用。
在递归调用中，我们再次进行递归调用 exgcd(b, a % b, y, x)，其中 b = 6，a % b = 0。这一次，我们将 y 和 x 的引用传递给递归调用。
由于 a % b = 0，递归调用结束，我们开始递归返回。在递归返回的过程中，我们更新 x 和 y 的值。
在第一次递归返回时，我们有 x = 1，y = 0。这是因为在 b = 6 和 a % b = 0 的情况下，方程 ax + by = d 变为 6x + 0y = 6，所以 x 的系数为 1，y 的系数为 0。
在第二次递归返回时，我们有 x = 0，y = 1。这是因为在 b = 12 和 a % b = 6 的情况下，方程 ax + by = d 变为 12x + 6y = 6，所以 x 的系数为 0，y 的系数为 1。
在第三次递归返回时，我们有 x = 1，y = -2。这是因为在 b = 18 和 a % b = 12 的情况下，方程 ax + by = d 变为 18x + 12y = 6，所以 x 的系数为 1，y 的系数为 -2。
最终，我们得到的最大公约数为 d = 6，并且满足方程 ax + by = d 的整数解为 x = 1，y = -2。
通过交换 x 和 y 的位置，我们可以确保在递归返回时，x 对应的是方程 ax + by = d 中 x 的系数，y 对应的是方程中 y 的系数。这样，我们可以得到正确的结果。
4.1.2 测试优化
但是在测试时发现，当n输入为很大超出INT_MAX时，根据范围对数据类型进行修改，改为long long类型：
4.2 欧拉函数
4.2.1代码思路
（1）初始化一个变量ans为n，用于保存最终的欧拉函数值。
（2）使用一个循环从2开始遍历到n的平方根。在循环中，判断n是否能被当前的循环变量i整除，如果可以整除，则说明i是n的一个素因子。
（3）如果i是n的素因子，将ans减去ans/i，这是因为ans/i表示小于等于n且与n互质的数中，能被i整除的数的个数。
（4）在一个内部的while循环中，将n不断除以i，直到n不能再被i整除为止。这是为了将n中的所有i素因子全部约掉。
（5）如果循环结束后，n仍然大于1，则说明n本身是一个素数，将ans减去ans/n。
（6）最后，返回ans作为欧拉函数的值。
总结起来，这段代码通过遍历n的素因子，将与n互质的数的个数逐步减去，最终得到欧拉函数的值。
4.2.2 测试优化
但是在测试时发现，当n输入为10^10时结果超出INT_MAX，所以根据范围对数据类型进行修改，改为long long类型：
- 实验结果
5.1求逆元
5.1.1编译
方法一编译：
方法二编译：
5.1.2 运行
测试书中样例：
输入a=2，m=7，输出逆元4；
输入a=635，m=737，输出逆元513
输入很大的数：
虽然结果是没有逆元是正确的，但是其实是巧合，因为INT_MAX=2147483646也跟2不互质没有逆元，输入a=1时同理，因为1的逆元是1本身
当将m换成与2互质且大于INT_MAX的数理应有逆元，但是输出“没有逆元”错误
但是即使修改成long long类型还是运行3个小时还无法算出结果，但是在方法二中可以输出结果
方法二long long优化代码输出结果：
经定义a*a’%m=1验证2*11666666666667=23333333333334-23333333333333=1
5.2欧拉函数
5.2.1编译：
5.2.2运行测试：
输入10
输入100：
输入10^10：
超出INT_MAX范围，输出错误
优化后：（将int改为long long）
以上结果验证均正确
六、总结
本次实验用c++编程实现了求解逆元和欧拉函数。
其中根据逆元的两种定义对应了两种求解思路，分别是尝试取余为1以及广义欧几里得算法。根据两种思路可以确定对应的求解适应背景，尝试法适用于较小数，而广义欧几里得算法适用于较大整数。在计算时产生中间结果较大不易用int类型保存，可优化为long long保存变量值。
求解欧拉函数，根据其基本定义是不大于整数n的素因子个数。那么遍历计数找其素因子，并将与n互质的数的个数逐步减去，最终得到欧拉函数的值。同理，在计算时产生中间结果较大不易用int类型保存，可优化为long long保存变量值，输入相同较大数进行测试看出优化后可以成功输出结果。