原根(扩展欧几里得的应用)
5星 · 超过95%的资源 需积分: 50 78 浏览量
2015-08-12
00:36:28
上传
评论 1
收藏 286KB PDF 举报 
第 4 章 指数与原根
在一个模 的既约剩余系中，如果一个元素的指数恰好等于
m
)(m
φ
，则这个元素即为模
的一个原根．在存在原根的既约剩余系中，每个元素均可以表示成原根的幂，反过来原根的幂
所表示的所有不同的元素恰好构成既约剩余系，这就给出了一种构造模
m
的既约剩余系的很自
然的一种方法．但只有 时才有原根，对于不存在原根的模 ，它的既约
剩余系是怎样构造的呢？以上所描述的结论与问题正是本章所要研究的主要内容．另外，本章
还介绍指数、指标两个主要概念及性质，其中指标为密码学中的离散对数问题．离散对数问题
是设计许多公钥密码算法的重要理论根据．
m
αα
ppm 2,,4,2,1=
m
§1 指数及其性质
首先我们给出指数及其原根的概念．
定义 1 设 ， ． 使式
1≥m
1),( =ma
)(mod1 ma
d
≡
成立的最小的正整数
d
称为 对模 的指数（习惯上也称为阶或周期），记作
a m
)(a
m
δ
．当
)()( ma
m
φ
δ
=
时，称 是模 的原根．
a m
性质 1 设 ， ．对任意整数 ，如果
1≥m
1),( =ma
d
)(mod1 ma
d
≡
，
则
da
m
)(
δ
．
证明 设
)(
0
ad
m
δ
=
，则 ，
rqdd +=
0 0
0 dr
<
≤
)(mod011)(11
00
maaaaa
rrq
drqd
d
≡−≡−=−=−
+
因为 ，所以由指数的定义得
0
0 dr <≤
0
=
r
．得证．
指数还具有以下特性：
６７
剩余24页未读，继续阅读
资源评论
qq_209251772015-08-12很不错的资源~~收藏了
