原根和其应用

《原根和其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、安庆师范学院数学与计算科学学院2009届毕业论文原根及其应用作者：×××指导老师：×××摘要本文介绍了指数与原根的定义以及它们的一些有关性质，并给出了关于模的原根存在的几个充分必要条件.从原根与同余方程解的关系角度揭示了当模存在原根时所具有的一些本质特性.最后讨论了基于离散对数问题的公钥密码体制即ElGamal密码体制，体现了原根在密码学方面的应用.关键词指数原根剩余类ElGamal密码体制1引言在这篇文章中，我们从欧拉定理引出指数的定义，进而得出原根定义，以及指数与原根的一些有关性质，接着我们经验证前

2、30个正整数的原根存在的情况推断出一般整数原根存在的条件，并给出证明.还从原根与同余方程解的关系这个角度出发，揭示了当模的原根存在时所具有的一些本质特性.最后讨论基于离散对数问题的公钥密码体制即ElGamal密码体制，体现了原根在密码学方面的应用.2整数指数与原根的定义及其性质2.1整数指数的定义.欧拉定理设是大于1的整数，，则.这里的是个欧拉数，即它在正整数上的值等于序列0，1，2，…，中与互质的数的个数.这就是说，若，，则至少存在一个正整数，满足.因此也存在满足上述要求的最小正整数，故有定义2.1若

3、，，则使得同余式成立的最小正整数叫做对于模的指数，记为.例2.1找2对于模7的指数.解因为，，，所以.同样找3对模7的指数.因为，，，，，，所以.要求出满足同余式的所有解，我们可用以下定理：定理2.1若，，则是的解的充要条件是：.第13页共12页安庆师范学院数学与计算科学学院2009届毕业论文证明（充分性）若，则，其中为一个正整数，因此由，知，所以.（必要性）若，则令，，则所以，因此.由指数定义知，是使成立的最小正整数.又因为，所以.即，亦即.例2.2判断及是否为的解.解由例2.1知，因为3不被10整除

4、，，因此由定理2.1知，不是的解，而是的解.推论2.1若，，则.证明因为，由欧拉定理知，，再由定理2.1知，.例2.3求出7对模9的指数.解因为小于9且与9互质的正整数有1，2，4，5，7，8，即，又因为6的因子为1，2，3，6，所以由推论2.1知，只可能是其中一数.又因为，，，所以.定理2.2若，，则当且仅当，其中，都是非负整数.证明若，不妨设，则，是正整数.第13页共12页安庆师范学院数学与计算科学学院2009届毕业论文因为，所以.若，其中，则由知，，因为，所以，再由定理2.1知，，即.例2.4设，

5、由定理2.2可知，但与不同余于模14.因为,，但9与20不同余于模6.2.2原根的定义我们再来给出原根的定义.定义2.2若，，且，则称为模的一个原根.例2.5显然，，所以3是模7的一个原根.同样，，所以5也是模7的一个原根.注并不是所有的模都存在原根.例如：对于模8，小于8且与8互质的数是1，3，5，7，即，而，，所以模8不存在原根.2.3指数与原根的性质.2.3.1关于指数的性质性质2.1若对于模的指数是，，，则对于模的指数是.证明因为，所以，因此对于模的指数是存在的.设对于模的指数是，则.由定理2.

6、1，，因而.又因为是对于模的指数，所以.而是对于模的指数.由定理2.1，.其中，都是正整数，所以.性质2.2若对于模的指数是，对于模的指数是，并且，则对于模的指数是.证明因，故.所以对于模的指数是存在的，且设为第13页共12页安庆师范学院数学与计算科学学院2009届毕业论文，则.所以.由定理2.1即得.又因为，所以.同理可证.再由，即得.又因为.由定理2.1知，.因为，，所以.2.3.2关于原根的性质性质2.3若，，如果是模的一个原根，则，，…，构成模的简化剩余类.性质2.4若，是一个正整数，则.证明令

7、，，，，则，.因为，所以，因此.由定理2.1知，.又因为，所以，则，所以，又因为，所以，因此，所以，即.例2.6根据例2.1，，则由性质2.3.4知，.推论2.2若是模的一个原根，为整数，且，则是模的一个原根是充要条件是.证明由性质2.4知，.所以是模的一个原根.3原根存在的条件任给一个模，原根是一定存在的吗？在接下来的内容中，我们的主要工作就是确定哪些整数的原根是存在的.第13页共12页安庆师范学院数学与计算科学学院2009届毕业论文我们可以验证在前30个正整数中，模2，3，4，5，6，7，9，10，

8、11，13，14，17，18，19，22，23，25，26，27，29存在原根，而8，12，15，16，20，21，24，28，30的原根不存在.通过观察，在此范围之内，任意的质数都有原根（2，3，5，7，11，13，17，19，23，29），另外9（），25（），27（）有原根，而6，10，14，18，22，26是单质数的两倍或单质数平方的两倍，剩下2和4也有原根，那么猜想：只有当模为2，4，，四者之一时，其中为单质数，为正整数，此模才有