(Zn*, ×) 中生成元的搜索算法一、实验目的 1. 该实验为综合性实验。 2. 通过本实验使学生掌握对生成元的计算, 加强学生对生成元的理解。二、实验内容 1. 判断(Zn*, ×) 中生成元是否存在:即 n=2,4 , p^l,2p^l 时( p 是奇素数) ,生成元存在; 2. 对欧拉函数进行因子分解, 列出不同素因子 q1,q2,......qk ; 3. 利用如下式子计算出(Zn*, ×) 的生成元: 4. 进一步搜索出所有生成元 g^d,(d,f(n))=1 。三、实验要求利用从左向右或从右向左算法进行模幂运算, 找出生成元 g 之后, 依次计算它的幂次,由此验证是否可以遍历整个群。四、实验原理当一个数的乘方可以生成一个群的所有元时称之为生成元。对于一个简化剩余系中当一个数的阶等于欧拉函数时其为该缩系的生成元。五、实验步骤 1. 提示用户输入需要计算其生成元的数。 2. 判断该数是否存在生成元,若没有输出错误。 3.当 n=2 时直接输出其生成元。 4. 其他情况下,分解该数的素因子。 5. 计算欧拉函数,并分解欧拉函数的素因子。 6. 求出缩系。 7. 根据公式计算该数的生成元。六、流程图,实验设计思路不存在生成元存在生成元输入数字为 2 不为 2 实验截图输入数字分解该数的素因子计算数的欧拉函数分解欧拉函数的素因子求出缩系得出生成元七、实验体会在实验的过程中, 有许多细节需要把握, 例如素因数分解过程中我就讲函数的返回值搞反, 改了很久才查出来, 这可以看出我们写程序的时候思路一定要清晰明确, 变量要尽量做到见名识意, 并且函数的返回值最好要有注释, 以便第二遍检查程序, 程序中会使用到很多的循环和数组,尽量要规定足够的数组大小和循环次数以防数据的丢失,最好是将一步步的程序结果用 printf 打印大屏幕上,这样可以清晰明了的看出哪一步出了问题,一边修改。
全文预览
