浅议论文范文.doc

　　浅议论文范文 浅议论文范文_论文范文导读：指导老师：×××本文介绍了指数与原根的定义以及它们的一些有关性质，并给出了关于模m的原根存在的几个充分必要条件.从原根与同余方程解的关系角度揭示了当模m存在原根时所具有的一些本质特性.最后讨论了基于离散对数问题的公钥 体制即ElGamal 体制，体现了原根在 学方面的应用.关键词指数原根剩余类ElGam 安庆师范学院数学与计算科学学院 2009 届毕业论文 原 根 及 其 应 用：××× 摘 要 指导老师：××× 本文介绍了指数与原根的定义以及它们的一些有关性质，并给出了关于模 m 的原根存 在的几个充分必要条件.从原根与同余方程解的关系角度揭示了当模 m 存在原根时所具有的一些 本质特性.最后讨论了基于离散对数问题的公钥 体制即 ElGamal 体制，体现了原根在 学方面的应用. 关键词 指数 原根 剩余类 ElGamal 体制 1 引言 在这篇文章中，我们从欧拉定理引出指数的定义，进而得出原根定义，以及指数与原根 的一些有关性质，接着我们经验证前 30 个正整数的原根存在的情况推断出一般整数原根存在 的条件， 并给出证明. 还从原根与同余方程解的关系这个角度出发， 揭示了当模 m 的原根存在 时所具有的一些本质特性.最后讨论基于离散对数问题的公钥 体制即 ElGamal 体制， 体现了原根在 学方面的应用. 2 整数指数与原根的定义及其性质 2.1 整数指数的定义.欧拉定理 设 m 是大于 1 的整数， (a, m) 1 ，则 a ( m) 1(mod m) . 这里的 (m) 是个 欧拉数，即它在正整数 m 上的值等于序列 0，1，2，…， a 1 中与 a 互质的数的个数. 这就是说，若 (a, m) 1 ， m 1，则至少存在一个正整数 r ，满足 a 1(mod m) . 因此r 也存在满足上述要求的最小正整数，故有 定义 2.1 若 m 1，(a, m) 1 ，则使得同余式 a 1(mod m) 成立的最小正整数 r 叫做r a 对于模 m 的指数，记 r 为 ordm a .例 2.1 找 2 对于模 7 的指数. 解 因为 2 2(mod 7) ， 2 4(mod 7) ， 2 1(mod 7) ，所以 ord7 2 3 . 同样找 3 对模 7 的指数. 因为 31 3(mod 7) ， 32 2(mod 7) ， 33 6(mod 7) ， 34 4(mod 7) ， 35 5(mod 7) ， 36 1(mod 7) ，所以 ord7 3 6 .要求出满足同余式 a 1(mod m) 的所有解 x ，我们可用以下定理：x 定理 2.1 若 (a, m) 1 ， m 0 ，则 x 是 a 1(mod m) 的解的充要条件是： ordm a | x .x 第 1 页 共 12 页 安庆师范学院数学与计算科学学院 2009 届毕业论文 证明 （充分性）若 ordm a | x ，则 x k ordm a ，其中 k 为一个正整数，因此 a x a k ordm a (a ordma ) k由 (a, m) 1 ，知 aordm a 1(mod m) ，所以 a 5 6 7 8 9 10 浅议论文范文_论文范文(2)导读：miji，j都是非负整数.证明dma，k是正整数.不妨设0ji，则ijkor;;若ij(modordma)，aiajkordma(aordma)kaj因为aordma1(modm)，所以第2页共12页安庆师范学院数学与计算科学学院2009届毕业论文ai(aordma)kajaj(modm).;;若aiaj(modm)，其 x (a ordm a ) k 1(mod m) . （必要性）若 a 1(mod m) ，则令 x q ordm a r ， 0 r ordm a ，则x a x a qordma r (a ordm a ) q a r a r (mod m)所以 a 1(mod m) ， 因此 a 1(mod m) . 由指数定义知，y ordm a 是使 a 1(mod m) 成x r y 立的最小正整数.又因为 0 r ordm a ，所以 r 0 .即 x q ordm a ，亦即 ordm a | x . 例 2.2 判断 x 10 及 x 15 是否为 2 1(mod 7) 的解.x 解x 由例 2.1 知 ord7 2 3 ，因为 3 不被 10 整除， 3 | 15 ，因此由定理 2.1 知， x 10 不x 是 2 1(mod 7) 的解