《数论算法》教案 5章(原根与离散对数).doc

《数论算法》教案_5章(原根与离散对数)原根与离散对数
内容
整数的阶
原根
有原根的整数
离散对数(指标)
要点
原根及其意义
有原根的整数的条件
离散对数及其性质
阶及其基本性质
准备知识:
欧拉定理:m>1,(a, m)=1,则
≡1(mod m)
问题:
①是否是使得上式成立的最小正整数?
②该最小正整数有何性质?
阶和原根概念
【】设m>1,(a, m)=1,则使得
≡1(mod m)
成立的最小正整数e叫做a对模m的阶(或指数),记作(a)。若a的阶e=,则a叫做模m的原根。
应用:Diffie—Hellman密钥交换算法
公钥算法的核心:
仅依赖公开信息不足以对算法构成威胁;
掌握私钥者可轻易获得信内容。
全局公开量
q 素数
q的原根(<q)
生成用户密钥
用户A
选择秘密的<q
计算公开的≡(mod q)
用户B
选择秘密的<q
计算公开的≡(mod q)
…
……
交换公开密钥
A→B:
B→A:
生成公共密钥K
用户A
计算 K≡(mod q)
用户B
计算 K≡(mod q)
说明:K≡≡≡(mod q)
例:
素数q=353,原根α=3
A选=97, 计算≡≡40 mod 353
B选=233, 计算≡≡248 mod 353
A与B交换
A计算密钥 K≡≡160 mod 353
B计算密钥 K≡≡160 mod 353
用定义求阶和原根
【例1】(按定义求阶和原根)m=7,则(7)=6。且
≡1,≡1,≡1,≡1,≡1,≡1(mod 7)
故对模数7而言,1,2,3,4,5,6的阶分别为1,3,6,3,6,2。列表表示为
a
1
2
3
4
5
6
(a)
1
3
6
3
6
2
因此,3,5是模7的原根。
【例2】(快速求阶)m=14=2·7, (14)=6,则
≡1,≡-1,≡-1,≡1,
≡1,≡1(mod 7)
列表
a
1
3
5
9
11
13
(a)
1
6
6
3
3
2
故3,5是模14的原根。
【例3】(无原根的整数)m=15=3·5, (15)=8,则
a
1
2
4
7
8
11
13
14
(a)
1
4
2
4
4
2
4
2
故模数15没有原根。
同理,可知模数m=9时,其原根为2,5;而整数8则没有原根。
也可以计算验证5是模3、6、9、18的原根。
阶的性质
【】设m>1,(a, m)=1,d为正整数,则
≡1(mod m) (a) │d
即d≡0(mod (a))
(证)充分性:设(a) │d,则d=k·(a),从而
≡≡≡1(mod m)
必要性:反证:若≡1且(a) d,则由欧几里得除法,有
d≡(a)·q+r, 0<r<(a)
从而
≡≡≡1(mod m)
与(a)的最小性矛盾。
【推论1】(a) │(m)。
意义:(a)必是(m)的因子,故求(a)只需计算,其中i│(m)。
【例4】()(例7)求(5)的值。
(解)(17)=16,只需计算(mod 17),其中d=1,2,4,8,16(实际上不必计算)。
≡5,≡8,≡13≡-4,≡16≡-1(mod 17)
所以,(5)=16,即5是模17的原根。
【例5】求(4)、(5)、(7)的值。
(解)(33)=20。
只需计算、、(mod 33)(i=1, 2, 4, 5, 10)。
≡1(mod 33);
≡23(mod 33),≡1(mod 33);
≡10(mod 33),≡1(mod 33)
∴(4)=5,(5)=10,(7)=10
【推论2】设p是奇素数,也是奇素数,pa,则
(1)若a是模p的二次剩余,则a不是p的原根,且当a≡1(mod p)时,(a)=1;当a1(mod p)时,(a)=;
(2)若a是模p二次非剩余,则当a≡p-1(mod p)时,(a)=2;当ap-1(mod p)时,(a)=p-1。
(3)此时,p有-1=个原根。
(4)当=2为偶素数时,必有p=5,其平方剩余为1和-1≡4,平方非剩余为2和3,且2和3是原根。
(证)由推论1,(a)│(p)=p-1=2·,故(a)可能为1, 2, , p-1。
(1)a是模p二次剩余,则由二次剩余的充分必要条件知
≡1(mod p)
(a)│,但是素数,故
(a)=1或
而(a)=1 a≡1(mod p),故结论成立。
(2)a是模p的二次非剩余,则由二次剩余的充分必要条件知≡-1(mod p)