文档介绍：浅议论文范文
浅议论文范文_论文范文导读:指导老师:×××本文介绍了指数与原根的定义以及它们的一些有关性质, 体制,
安庆师范学院数学与计算科学学院 2009 届毕业论文
原根及其应用:××× 摘要指导老师:×××
本文介绍了指数与原根的定义以及它们的一些有关性质,并给出了关于模 m 的原根存
m ElGamal 体制,体现了原根在学方面的应用.
关键词指数原根剩余类 ElGamal 体制
1
引言
在这篇文章中,我们从欧拉定理引出指数的定义,进而得出原根定义,以及指数与原根的一些有关性质,接着我们经验证前 30 个正整数的原根存在的情况推断出一般整数原根存在的条件, 并给出证明.
还从原根与同余方程解的关系这个角度出发, 揭示了当模 m ElGamal 体制, 体现了原根在学方面的应用.
2
整数指数与原根的定义及其性质
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
也存在满足上述要求的最小正整数,故有定义 若 m 1,(a, m) 1 ,则使得同余式 a 1(mod m) 成立的最小正整数 r 叫做r
a 对于模 m 的指数,记 r 为 ordm a .例 找 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
定理 若(a, m) 1 , m 0 ,则 x 是 a 1(mod m) 的解的充要条件是: ordm a | x .x
安庆师范学院数学与计算科学学院 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,,,则ijkor;;若ij(modordma),aiajkordma(aordma)kaj因为aordma1(modm),所以
安庆师范学院数学与计算科学学院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 .
例 判断 x 10 及 x 15 是否为 2 1(mod 7)
解x
由例 知 ord7 2 3 ,因为 3 不被 10 整除, 3 | 15 ,因此由定理 知, x 10 不x
是 2 1(mod 7) 的解,而 x 15 是 2 1(mod 7) 的解.
推论 若(a, m) 1 , m 0 ,则 ordm a | (m) .
证明因为(a, m) 1 ,由欧