《数论算法》 第五章 原根与离散对数

第 5 章 原根与离散对数

1. 整数的阶 内容 2. 原根 3. 有原根的整数 4. 离散对数（指标） 1. 原根及其意义 要点 2. 有原根的整数的条件 3. 离散对数及其性质 5.1 阶及其基本性质

准备知识：

（1） 欧拉定理：m＞1，(a, m)＝1，则

a??m?≡1（mod m）

（2） 问题：

①??m?是否是使得上式成立的最小正整数？ ②该最小正整数有何性质？ (一) 阶和原根概念

【定义5.1.1】设m＞1，(a, m)＝1，则使得

ae≡1（mod m）

成立的最小正整数e叫做a对模m的阶（或指数），记作

ordm(a)。若a的阶e＝??m?，则a叫做模m的原根。(二) 应用：Diffie—Hellman密钥交换算法 公钥算法的核心：

（1） 仅依赖公开信息不足以对算法构成威胁； （2） 掌握私钥者可轻易获得信内容。

1/58

《数论算法》 第五章 原根与离散对数

全局公开量

q 素数

? q的原根（?＜q） 用户A 用户B …

交换公开密钥

A→B： YA B→A： YB

生成公共密钥K 用户A 计算 K≡?YB?用户B 计算 K≡?YA?说明：K≡?YB?例：

? 素数q＝353，原根α＝3

? A选XA＝97， 计算YA≡397≡40 mod 353 ? B选XB＝233， 计算YB≡3233≡248 mod 353 ? A与B交换

? A计算密钥 K≡24897≡160 mod 353 ? B计算密钥 K≡40233≡160 mod 353

(三) 用定义求阶和原根

2/58

XAXA生成用户密钥 选择秘密的XA XA＜q 计算公开的YA YA≡?XA（mod q） 选择秘密的XB XB＜q 计算公开的YB YB≡?XB（mod q） …… （mod q） （mod q） XB≡?YA?XB≡?XAXB（mod q）

《数论算法》 第五章 原根与离散对数

【例1】（按定义求阶和原根）m＝7，则?(7)＝6。且

11≡1，23≡1，36≡1，43≡1，56≡1，62≡1（mod 7） 故对模数7而言，1，2，3，4，5，6的阶分别为1，3，6，3，6，2。列表表示为

a 1 2 3 3 6 4 3 5 6 6 2 ordm(a) 1

因此，3，5是模7的原根。 【例2】（快速求阶）m＝14＝2·7， ?(14)＝6，则

11≡1，33≡－1，53≡－1，93≡1，

113≡1，132≡1（mod 7）

列表

a 1 3 6 5 6 9 3 11 13 3 2 ordm(a) 1 故3，5是模14的原根。

【例3】（无原根的整数）m＝15＝3·5， ?(15)＝8，则

a 1 2 4 4 2 7 4 8 4 11 13 14 2 4 2 ordm(a) 1 故模数15没有原根。

同理，可知模数m＝9时，其原根为2，5；而整数8则没有原根。

也可以计算验证5是模3、6、9、18的原根。

3/58

《数论算法》 第五章 原根与离散对数

(四) 阶的性质

【定理5.1.1】设m＞1，(a, m)＝1，d为正整数，则

ad≡1（mod m） ? ordm(a) │d

即d≡0（mod ordm(a)）

（证）充分性：设ordm(a) │d，则d＝k·ordm(a)，从而

a≡adk?ordm?a?≡ad?ordm?a?k?≡1（mod m）

必要性：反证：若a≡1且ordm(a) d，则由欧几里得除法，有

d≡ordm(a)·q＋r， 0＜r＜ordm(a)

从而

a≡aarr?ordm?a?q?≡ad≡1（mod m）

与ordm(a)的最小性矛盾。

【推论1】ordm(a) │?(m)。

意义：ordm(a)必是?(m)的因子，故求ordm(a)只需计算ai，其中i│?(m)。

【例4】（用定理5.1.1结论快速求阶及原根）（例7）求

ord17(5)的值。

（解）?(17)＝16，只需计算5d（mod 17），其中d＝1，2，4，8，16（实际上516不必计算）。

51≡5，52≡8，54≡13≡－4，58≡16≡－1（mod 17）

4/58