数论概论读书笔记 29.原根与指标（指标也被称为离散对数(#^.^#)）

2019-04-13 14:26发布生成海报

站内文章 / 模拟电子

9315 0

原根与指标（指标也被称为离散对数(#^.^#)）

原根我们清楚了。啥是指标呢？对于模13，2是它的原根，则

2^{x} m o d 13

会取遍

[1, 12]

，

x \in [1, 12]

比如

2^{4} = 16 \equiv 3 m o d (13)

则

I (3) = 4

这就是指标函数

I

显然，指标函数是双射函数 指标法则 指标满足下述法则：

证明：

g^{I (a b)} \equiv a b \equiv g^{I (a)} g^{I (b)} \equiv g^{I (a) + I (b)} (m o d p)

这意味着

g^{I (a b) - I (a) - I (b)} \equiv 1 (m o d p)

又

g

是原根，则

I (a b) - I (a) - I (b)

是

p - 1

的倍数所以乘积法则得证。幂法则同理。如果我们现在已经有了指标表（

p - 1

对映射），则可以通过指标法则求模和简化解同余式比如求

29^{14} m o d 37

，你可以使用快速幂也可以用指标法则。

I (29^{14}) \equiv 14 * I (29) \equiv 14 * 21 \equiv 6 m o d 36

又

I (27) = 6

，所以

29^{14} \equiv 27 (m o d 37)

指标法则也可以用来求同余式考虑同余式

19 x \equiv 23 (m o d 37)

则

I (19) + I (x) \equiv I (23) (m o d 36)

35 + I (x) \equiv 15 (m o d 36) " role="presentation">