MFIS-Lab4：求解指数和原根
信息安全数学基础
课程实验报告
实验报告（四）
系 别： 网络空间安全系
班 级： secret!
姓 名： secret!
学 号： secret!
实验时间： 2023年11月15日
指导老师： secret!
- 实验内容
- 实验目标
理解指数定义和求解思路，理解原根存在判断条件和求解过程，用c++编程实现，并在求解原根时优化算法并测试电脑计算性能。
- 实验原理 1.指数
2.原根
- 实验设计
实验共分为1个主函数和4个自定义函数。其中，主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出，isOddPrime函数是辅助函数判断模数p是否为奇素数的程序执行前提，Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根，也可在求原根优化时作为循环条件区间值，Exp函数是解答第一问的求指数函数，Prim函数是解答第二问的求模数p所有原根
- 定义变量和函数
主函数：
底数：a
模数：p
欧拉函数：elr
指数：ord
存放所有原根的数组roots
isOddPrime函数：
函数参数传入的模数：p
函数返回bool类型：true/false
Euler函数：
函数参数传入的模数：p
计数器：cnt
迭代递增指数：e
Exp函数：
函数参数传入的底数和模数：a和p
迭代递增计数器和返回值：e
存放余数的中间变量：result
Prim函数：
函数参数传入的模数：p
存放所有原根的数组stl容器：prim
欧拉函数：euler
迭代递增的底数g
判断是否为原根bool类型：isPrim
- 主函数
主函数负责部分基本变量定义、判断模数p是否为奇素数以及程序的输入和输出。首先读入底数a和模数p，通过调用isOddPrime函数判断p是否为奇素数，如果不是，则直接返回0并结束程序。
然后，通过调用Euler函数计算模p的欧拉函数值，并将结果赋给变量elr。这个中间结果在后面计算中多次用到，所以可以先提前计算出来。打印提示信息和elr结果。
接下来，通过调用Exp函数计算整数a模p的指数，并将结果赋给变量ord。打印提示信息和ord结果。
然后，通过调用Prim函数计算模p的所有原根，并将结果存储在名为roots的vector
- isOddPrime函数
isOddPrime函数是辅助函数判断模数p是否为奇素数
函数参数传入模数p，首先进行两个条件判断：如果p小于等于1，或者p是偶数，则返回false，因为偶数不可能是素数。 如果以上条件都不满足，那么进入循环。
循环从i=3开始，每次迭代增加2，因为偶数已经在前面的条件判断中排除了。循环条件是i * i <= p，即i的平方小于等于p。
在循环体中，判断p是否能被小于等于其平方根的奇数整除，来确定p是否为奇素数。如果能整除，则p不是素数，返回false。如果循环结束后仍然没有找到能整除p的数，则p是素数，返回true。
- Euler函数
Euler函数也是辅助函数求解模数p的欧拉函数在求解指数后可以判断该指数是否为原根，也可在求原根优化时作为循环条件区间值。
函数参数传入模数p，首先声明一个整数变量count，用于计数满足条件的数值。然后，通过一个for循环遍历从1到p-1的所有整数。
在循环体中，通过遍历从1到p-1的整数，计算与p互质的数值的个数，从而得到p的欧拉函数值。具体的通过调用库函数中的__gcd函数计算i和p的最大公约数。如果最大公约数等于1，说明i和p互质，即没有共同的因子，满足欧拉函数的定义。此时，将count加1。
循环结束后，count记录了满足条件的数值的个数，即p的欧拉函数值。将count作为函数的返回值。
- Exp函数
Exp函数是解答第一问的求指数函数，程序设计思想参考指数的定义。
函数参数传入底数a和模数p。函数首先声明一个整数变量e，用于记录指数的值，初始值为1。然后，声明一个整数变量result，用于存储a对模p的中中间结果。
通过使用循环来计算a的幂，直到结果等于1为止。在每次循环中，将结果乘以a并对p取模，同时记录循环的次数。最后返回循环的次数，也就是指找到最小的正整数e，使得a^e ≡ 1 (mod p)。
- Prim函数
Prim函数是解答第二问的求模数p所有原根，上图展示的优化后的算法，优化过程如下：
如果按照原根存在的充要条件实现需要2个函数和3重for循环。首先PrimeQ函数求解整数p-1的所有素因子，q数组容器存放所有的素因子，PrimeQ函数内部通过双重for循环，外层for循环判断i是否能被p整除，内层for循环再判断因子是否是素数，如果满足就向容器中插入p-1/i
Prime1函数计算所有原根。使用3重for循环，第一层for循环遍历2到小于p的整数，第二层for循环遍历计算的p-1/i，将其依次作为指数，内层for循环累乘p-1/i次。
由此可见2个弊端：3层for循环是立方级别的运算，时间复杂度很高；muti累乘很容易超过数据类型的范围。
优化：考虑原根的性质，即它是指数且小于欧拉函数确定遍历范围，以及原根定义是指数等于欧拉函数确定判断条件；并且考虑用long long存放数据类型。合理灵活运用之前的两个函数：Euler函数的结果和Exp求指数函数。优化后仅用两重循环，降低时间复杂度。
函数接受一个长整型参数p，表示模数。它使用循环来遍历从2到p-1的所有整数，判断每个整数是否为模p的原根。
函数首先声明一个vector
接下来，通过一个for循环遍历从2到p-1的所有整数，用变量g表示当前整数，对每个整数进行指数计算调用Exp函数，若结果等于欧拉函数则为原根，插入容器中保存。
最后，将存储原根的prim容器作为函数的返回值。
- 实验结果
- 教材例5.1.1
题目：教材例5.1.1
输入解释：
依次输入：2 7，分别表示底数a和模数p
输出结果：
模p的欧拉函数是：6
整数a模p的指数是：3但不是原根
模p的所有原根共计2个，列举如下：3 5
与教材结果一致，正确
- 教材例5.2.1
题目：教材例5.2.1
输入解释：
依次输入：5 41，分别表示底数a和模数p
输出结果：
模p的欧拉函数是：40
整数a模p的指数是：20但不是原根
模p的所有原根共计16个，列举如下：6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
与教材结果一致，正确
- 教材例5.2.2
题目：
输入解释：
依次输入：9 43，分别表示底数a和模数p
输出结果：
模p的欧拉函数是：42
整数a模p的指数是：21但不是原根
模p的所有原根共计12个，列举如下：3 5 12 18 19 20 26 28 29 30 33 34
与教材结果一致，正确
- 测试电脑计算极限
找到素数表，多次输入尝试，发现输入p=46337时是实验电脑能计算的p的最大值，程序运行能在10秒内运算出结果
......（中间结果）
输入下一个更大的素数p=46349会计算不出结果：
六、总结
本次实验用c++编程实现了求解底数a模p的指数和模p的所有原根。在程序前提是p为奇素数的情况下，故先判断前提并且这里调用了c++的库函数__gcd求解最大公因数；进入程序先计算了模p的欧拉函数，这在判断原根时很有用；按照指数的定义编程求解；原根的求解方式有多种，经尝试发现用定义和性质而不是用原根存在性的充要条件会优化许多，因为可以利用之前的欧拉函数结论和再次调用求指数函数，并且时间复杂度也会明显降低。利用求原根还测试了电脑的性能，发现其极限是计算最大奇素数p=46337的原根。