第 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
.得证.
指数还具有以下特性:
67
- 1
- 2
前往页