指标
| 指标 | |
|---|---|
| 术语名称 | 指标 |
| 英语名称 | index |
| 别名 | 离散对数, discrete logarithm |
| 指标组 | |
|---|---|
| 术语名称 | 指标组 |
| 英语名称 | system of indices |
指标(index)指某个模数下，其简化剩余系中的某个数，被表示为其原根的幂时，所对应的指数，也对应这个循环群中的离散对数。
对没有原根的任意模，则可以将其拆解成多个底的幂之积，因此引入指标组(system of indices)概念，即将这个数表示为 -1 、 2 的幂及全部奇质因数幂下的原根的指数。
指标和指标组说明了最简剩余系的内部结构。
定义
有原根的模数
对整数 [math]\displaystyle{ b }[/math] ，正整数 [math]\displaystyle{ n }[/math] 有原根 [math]\displaystyle{ a }[/math] ，且 [math]\displaystyle{ \operatorname{gcd}(b, n) = 1 }[/math] ，有 [math]\displaystyle{ (\exists! i) (0\leq i \lt \varphi(n) \land a^i = b) }[/math] ，此时称整数 [math]\displaystyle{ i }[/math] 为整数 [math]\displaystyle{ b }[/math] 对模 [math]\displaystyle{ n }[/math] 的以 [math]\displaystyle{ a }[/math] 为底的指标(index of [math]\displaystyle{ b }[/math] to the base [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math] )，记作 [math]\displaystyle{ \operatorname{ind}_a b \pmod n }[/math]，也有人记作 [math]\displaystyle{ \gamma_{n,a}(b) }[/math] 。上下文可说明的情况下，也可以记作 [math]\displaystyle{ \operatorname{ind}_a b }[/math] 、 [math]\displaystyle{ \gamma_{a}(b) }[/math] 或 [math]\displaystyle{ \gamma(b) }[/math]。
2 的幂的模数
对整数 [math]\displaystyle{ b }[/math] ，正整数 [math]\displaystyle{ n }[/math] 若满足 [math]\displaystyle{ n = 2^k ,k\geq 3 }[/math] ，且 [math]\displaystyle{ \operatorname{gcd}(b, 2) = 1 }[/math] ，有[math]\displaystyle{ (\exists! (r,i), r = 0,1, 0\leq i \lt \varphi(n)) ((-1)^r a^i = b) }[/math] ，此时称整数对 [math]\displaystyle{ (r, i) }[/math] 为整数 [math]\displaystyle{ b }[/math] 对模 [math]\displaystyle{ 2^k }[/math] 的以 [math]\displaystyle{ -1, a }[/math] 为底的指标组(system of indices)，记作 [math]\displaystyle{ \gamma^{(-1)}_{n,a}(b), \gamma^{(0)}_{n,a}(b) }[/math] 。上下文可说明的情况下，也可以记作 [math]\displaystyle{ \gamma^{(-1)}_{a}(b) }[/math] 或 [math]\displaystyle{ \gamma^{(-1)}(b) }[/math] 等。
这里的指标也可以看作在某个模数同余下的最小非负剩余，对一般的正整数 [math]\displaystyle{ k }[/math] ，可以记 [math]\displaystyle{ r, i }[/math] 的模分别为 [math]\displaystyle{ c_{-1}(k), c_{0}(k) }[/math] ，如果取底数为 5 ，有：
[math]\displaystyle{ c_{-1}(k) = \begin{cases} 1 &, k = 1 \\ 2 &, k \geq 2\end{cases} }[/math]
[math]\displaystyle{ c_{0}(k) = \begin{cases} 1 &, k = 1 \\ 2^{k-2} &, k \geq 2\end{cases} }[/math]
其中是因为 [math]\displaystyle{ \operatorname{ord}_{2^k}(5) = 2^{k-2} }[/math] 。
一般合数的模数
对一般的模 [math]\displaystyle{ n = 2^{k_0} p_1^{k_1} p_2^{k_2} \dots p_r^{k_r} }[/math] ，其中 [math]\displaystyle{ p_i }[/math] 是不同的奇质数，记
[math]\displaystyle{ c_{-1} = c_{-1}(k_0), c_0 = c_{0}(k_0) }[/math]
是 2 的幂相关的两个指标的模，
[math]\displaystyle{ c_i = \varphi(p_i^{k_i}) }[/math]
是对各个奇质数幂的指标的模，
记 [math]\displaystyle{ p_0 = 2 }[/math] ，类似中国剩余定理的思想，按 [math]\displaystyle{ n = p_i^{k_i} M_i, 0\leq i \lt r }[/math] 记剩余部分 [math]\displaystyle{ M_i }[/math] ，并记其在各自模下的逆 [math]\displaystyle{ M_i^{-1} }[/math] 满足 [math]\displaystyle{ M_i M_i^{-1} \equiv 1 \mod{p_i^{k_i}} }[/math] ，
则分别考虑在每个质数幂模下的指标剩余的关系，可知对最简剩余系中的任意 [math]\displaystyle{ x }[/math] ，一定存在唯一的一组 [math]\displaystyle{ \gamma^{(-1)}, \gamma^{(0)}, \dots, \gamma^{(r)} }[/math] ，满足 [math]\displaystyle{ 0\leq \gamma^{(i)} \lt c_i }[/math] ，且使得
[math]\displaystyle{ x \equiv M_0 M_0^{-1} (-1)^{\gamma^{(-1)}} 5^{\gamma^{(0)}} + M_1 M_1^{-1} g_1^{\gamma^{(1)}} + M_2 M_2^{-1} g_2^{\gamma^{(2)}} + \dots + M_r M_r^{-1} g_r^{\gamma^{(r)}} \pmod{n} }[/math]
其中 [math]\displaystyle{ g_i }[/math] 是以各个 [math]\displaystyle{ p_i^{k_i} }[/math] 为模的原根。
因此，对整数 [math]\displaystyle{ a }[/math] ，称分段的元组 [math]\displaystyle{ (\gamma^{(-1)}(a), \gamma^{(0)}(a) ; , \gamma^{(1)}(a), \gamma^{(2)}(a), \dots, \gamma^{(r)}(a) ) }[/math] 为整数 [math]\displaystyle{ a }[/math] 对模 [math]\displaystyle{ n }[/math] 的以 [math]\displaystyle{ -1, 5; g_1, g_2, \dots, g_r }[/math] 为底的指标组(system of indices of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math] )，记作 [math]\displaystyle{ \gamma_n(a) }[/math] 。
性质
对于模数有原根的情况：
- [math]\displaystyle{ g^h \equiv g^k \equiv a \pmod n \Leftrightarrow h\equiv k \equiv \gamma_{n,g}(a) \pmod{\varphi(n)} }[/math] ；
- [math]\displaystyle{ g }[/math] 是模 [math]\displaystyle{ n }[/math] 的原根， [math]\displaystyle{ \operatorname{gcd}(ab,n)=1 }[/math] ，则有 [math]\displaystyle{ \gamma_{n,g}(ab) \equiv \gamma_{n,g}(a) + \gamma_{n,g}(b) \pmod \varphi(n) }[/math] ；
- [math]\displaystyle{ \gamma_{n,g}(a^m) \equiv m \gamma_{n,g}(a) \pmod \varphi(m) }[/math]
- 如果模 [math]\displaystyle{ n }[/math] 有两个不同原根 [math]\displaystyle{ g }[/math] 和 [math]\displaystyle{ g' }[/math] ，对任意 [math]\displaystyle{ \operatorname{gcd}(a,n)=1 }[/math] ，有 [math]\displaystyle{ \gamma_{n,g'}(a) \equiv \gamma_{n,g'}(g) \gamma_{n,g}(a) \pmod{\varphi(n)} }[/math] ，可以类比换底公式；
- [math]\displaystyle{ g }[/math] 是模 [math]\displaystyle{ n }[/math] 的原根， [math]\displaystyle{ \operatorname{gcd}(a,n)=1 }[/math] ，则有 [math]\displaystyle{ \operatorname{ord}_n (a) = \tfrac{\varphi(n)}{\operatorname{gcd}(\gamma_{n,g}(a), \varphi(n))} = \tfrac{\operatorname{lcm}(\gamma_{n,g}(a), \varphi(n))}{\gamma_{n,g}(a)} }[/math]
对于 2 的幂的情况，如果取底数为 5 （此时有 [math]\displaystyle{ \operatorname{ord}_{2^k} 5 = 2^{k-2} }[/math] ）：
- 对任意 [math]\displaystyle{ a \equiv (-1)^j 5^h \pmod{2^k} }[/math] ，有 [math]\displaystyle{ j \equiv \gamma^{-1}_{2^k,5}(a) \equiv \tfrac{a-1}{2} \pmod 2 }[/math] ， [math]\displaystyle{ h \equiv \gamma^{(0)} \pmod{2^{k-2}} }[/math]
- 若 [math]\displaystyle{ \operatorname{gcd}(ab, 2) = 1 }[/math] ，则
- [math]\displaystyle{ \gamma^{(-1)}(ab) \equiv \gamma^{(-1)}(a)+\gamma^{(-1)}(b) \pmod 2 }[/math]
- [math]\displaystyle{ \gamma^{(0)}(ab) \equiv \gamma^{(0)}(a)+\gamma^{(0)}(b) \pmod {2^{k-2}} }[/math]
- 若 [math]\displaystyle{ \operatorname{gcd}(a,2) = 1 }[/math] ，则
- [math]\displaystyle{ \delta_{2^k}(a) = \begin{cases} \tfrac{2^{k-2}}{\operatorname{gcd(\gamma^{(0)}(a), 2^{k-2})}} &, 0 \lt \gamma^{(0)}(a) \lt 2^{k-2} \\ \tfrac{2}{\operatorname{gcd}(\gamma^{(-1)}(a), 2)} &, \gamma^{(0)}(a) = 0 \end{cases} }[/math]
- 记模 [math]\displaystyle{ 2^k, (k\geq3) }[/math] 的最简剩余系中乘法阶数为 [math]\displaystyle{ d (d\geq 1, d \mid 2^{k-2}) }[/math] 的元素个数为 [math]\displaystyle{ \psi(d) }[/math] ，则有
- [math]\displaystyle{ \psi(d) = \begin{cases} 1 &, d=1 \\ 3 &, d=2 \\ 2\varphi(d) &, 2 \lt d\mid 2^{k-2} \end{cases} }[/math]