一、指数(离散对数)
定义
设 g 是模 m 的一个原根(即 ordm(g)=φ(m)). 则对任意满足 gcd(a,m)=1 的 a,存在唯一的整数 t(0≤t<φ(m))使得
a≡gt(modm)
称 t 为 a 对底数 g 的指数,记作 indg(a)=t(也常写作 ind(a) 当底数明确时).
指数可以理解为模 m 下的”对数”:a=gindg(a)(modm).
性质 1 — 指数的模
a≡b(modm)⟺ind(a)≡ind(b)(modφ(m))
性质 2 — 乘法变加法
ind(ab)≡ind(a)+ind(b)(modφ(m))
这恰如对数 log(ab)=loga+logb.
性质 3 — 幂次变乘法
ind(ak)≡k⋅ind(a)(modφ(m))
性质 4 — 换底公式
若 g1,g2 都是模 m 的原根,则
indg2(a)≡indg2(g1)⋅indg1(a)(modφ(m))
性质 5 — 次数与指数的关系
设 ordm(a)=l,则 gcd(ind(a),φ(m))=lφ(m).
特别地,a 是原根 ⟺ gcd(ind(a),φ(m))=1.
证明:al≡1(modm)⟺gl⋅ind(a)≡1(modm)⟺φ(m)∣l⋅ind(a).
令 d=gcd(ind(a),φ(m)),则 dφ(m)∣l,而 l 是最小正指数使 al≡1,故 l=dφ(m). □
二、指数表
当模数 m 较小时,可以为每个与 m 互素的 a 列出其指数,形成指数表,方便求解同余式.
例题
模 7,取原根 g=3(φ(7)=6):
| a |
1 |
2 |
3 |
4 |
5 |
6 |
| ind3(a) |
0 |
2 |
1 |
4 |
5 |
3 |
验证:30≡1, 32=9≡2, 31=3, 34=81≡4, 35=243≡5, 33=27≡6(mod7).
利用指数表,同余式 ax≡b(modp) 可化为 ind(a)+ind(x)≡ind(b)(modp−1),从而 ind(x)≡ind(b)−ind(a)(modp−1),查表即得 x.