查看“︁指标”︁的源代码

[[分类:同余理论]]
{{InfoBox
|name=指标
|eng_name=index
|aliases=离散对数,discrete logarithm
}}
{{InfoBox
|name=指标组
|eng_name=system of indices
}}
'''指标'''('''index''')指某个模数下，其[[简化剩余系]]中的某个数，被表示为其[[原根]]的幂时，所对应的指数，也对应这个[[循环群]]中的[[离散对数]]。

对没有原根的任意模，则可以将其拆解成多个底的幂之积，因此引入'''指标组'''('''system of indices''')概念，即将这个数表示为 -1 、 2 的幂及全部奇质因数幂下的原根的指数。

指标和指标组说明了最简剩余系的内部结构。

== 定义 ==

=== 有原根的模数 ===

对整数 <math>b</math> ，正整数 <math>n</math> 有原根 <math>a</math> ，且 <math>\operatorname{gcd}(b, n) = 1</math> ，有
<math>(\exists! i) (0\leq i < \varphi(n) \land a^i = b)</math> ，此时称整数 <math>i</math> 为整数 <math>b</math> 对模 <math>n</math> 的以 <math>a</math> 为底的'''指标'''('''index''' of <math>b</math> to the base <math>a</math> modulo <math>n</math> )，记作 <math>\operatorname{ind}_a b \pmod n</math>，也有人记作 <math>\gamma_{n,a}(b)</math> 。上下文可说明的情况下，也可以记作 <math>\operatorname{ind}_a b</math> 、 <math>\gamma_{a}(b)</math> 或 <math>\gamma(b)</math>。

=== 2 的幂的模数 ===

对整数 <math>b</math> ，正整数 <math>n</math> 若满足 <math>n = 2^k ,k\geq 3</math> ，且 <math>\operatorname{gcd}(b, 2) = 1</math> ，有<math>(\exists! (r,i), r = 0,1, 0\leq i < \varphi(n)) ((-1)^r a^i = b)</math> ，此时称整数对 <math>(r, i)</math> 为整数 <math>b</math> 对模 <math>2^k</math> 的以 <math>-1, a</math> 为底的'''指标组'''('''system of indices''')，记作 <math>\gamma^{(-1)}_{n,a}(b), \gamma^{(0)}_{n,a}(b)</math> 。上下文可说明的情况下，也可以记作 <math>\gamma^{(-1)}_{a}(b)</math> 或 <math>\gamma^{(-1)}(b)</math> 等。

这里的指标也可以看作在某个模数同余下的最小非负剩余，对一般的正整数 <math>k</math> ，可以记 <math>r, i</math> 的模分别为 <math>c_{-1}(k), c_{0}(k)</math> ，如果取底数为 5 ，有：

<math>
c_{-1}(k) = \begin{cases} 1 &, k = 1 \\ 2 &, k \geq 2\end{cases}
</math>

<math>
c_{0}(k) = \begin{cases} 1 &, k = 1 \\ 2^{k-2} &, k \geq 2\end{cases}
</math>

其中是因为 <math>\operatorname{ord}_{2^k}(5) = 2^{k-2}</math> 。

=== 一般合数的模数 ===

对一般的模 <math>n = 2^{k_0} p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}</math> ，其中 <math>p_i</math> 是不同的奇质数，记

<math>
c_{-1} = c_{-1}(k_0), c_0 = c_{0}(k_0)
</math>

是 2 的幂相关的两个指标的模，

<math>
c_i = \varphi(p_i^{k_i})
</math>

是对各个奇质数幂的指标的模，

记 <math>p_0 = 2</math> ，类似[[中国剩余定理]]的思想，按 <math>n = p_i^{k_i} M_i, 0\leq i < r</math> 记剩余部分 <math>M_i</math> ，并记其在各自模下的逆 <math>M_i^{-1}</math> 满足 <math>M_i M_i^{-1} \equiv 1 \mod{p_i^{k_i}}</math> ，

则分别考虑在每个质数幂模下的指标剩余的关系，可知对最简剩余系中的任意 <math>x</math> ，一定存在唯一的一组 <math>\gamma^{(-1)}, \gamma^{(0)}, \dots, \gamma^{(r)}</math> ，满足 <math>0\leq \gamma^{(i)} < c_i</math> ，且使得

<math>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>g_i</math> 是以各个 <math>p_i^{k_i}</math> 为模的原根。

因此，对整数 <math>a</math> ，称分段的[[元组]] <math>(\gamma^{(-1)}(a), \gamma^{(0)}(a) ; , \gamma^{(1)}(a), \gamma^{(2)}(a), \dots, \gamma^{(r)}(a) )</math> 
为整数 <math>a</math> 对模 <math>n</math> 的以 <math>-1, 5; g_1, g_2, \dots, g_r</math> 为底的'''指标组'''('''system of indices''' of <math>a</math> modulo <math>n</math> )，记作 <math>\gamma_n(a)</math> 。

== 性质 ==

对于模数有原根的情况：

* <math>g^h \equiv g^k \equiv a \pmod n \Leftrightarrow h\equiv k \equiv \gamma_{n,g}(a) \pmod{\varphi(n)}</math> ；
* <math>g</math> 是模 <math>n</math> 的原根， <math>\operatorname{gcd}(ab,n)=1</math> ，则有 <math>\gamma_{n,g}(ab) \equiv \gamma_{n,g}(a) + \gamma_{n,g}(b) \pmod \varphi(n)</math> ；
** <math>\gamma_{n,g}(a^m) \equiv m \gamma_{n,g}(a) \pmod \varphi(m)</math>
* 如果模 <math>n</math> 有两个不同原根 <math>g</math> 和 <math>g'</math> ，对任意 <math>\operatorname{gcd}(a,n)=1</math> ，有 <math>\gamma_{n,g'}(a) \equiv \gamma_{n,g'}(g) \gamma_{n,g}(a) \pmod{\varphi(n)}</math> ，可以类比换底公式；
* <math>g</math> 是模 <math>n</math> 的原根， <math>\operatorname{gcd}(a,n)=1</math> ，则有 <math>\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>\operatorname{ord}_{2^k} 5 = 2^{k-2}</math> ）：

* 对任意 <math>a \equiv (-1)^j 5^h \pmod{2^k}</math> ，有 <math>j \equiv \gamma^{-1}_{2^k,5}(a) \equiv \tfrac{a-1}{2} \pmod 2</math> ， <math>h \equiv \gamma^{(0)} \pmod{2^{k-2}}</math>
* 若 <math>\operatorname{gcd}(ab, 2) = 1</math> ，则
** <math>\gamma^{(-1)}(ab) \equiv \gamma^{(-1)}(a)+\gamma^{(-1)}(b) \pmod 2</math>
** <math>\gamma^{(0)}(ab) \equiv \gamma^{(0)}(a)+\gamma^{(0)}(b) \pmod {2^{k-2}}</math>
* 若 <math>\operatorname{gcd}(a,2) = 1</math> ，则
** <math>\delta_{2^k}(a) = \begin{cases} \tfrac{2^{k-2}}{\operatorname{gcd(\gamma^{(0)}(a), 2^{k-2})}} &, 0 < \gamma^{(0)}(a) < 2^{k-2} \\ \tfrac{2}{\operatorname{gcd}(\gamma^{(-1)}(a), 2)} &, \gamma^{(0)}(a) = 0 \end{cases}</math>
* 记模 <math>2^k, (k\geq3)</math> 的最简剩余系中[[乘法阶数]]为 <math>d (d\geq 1, d \mid 2^{k-2})</math> 的元素个数为 <math>\psi(d)</math> ，则有
** <math>\psi(d) = \begin{cases} 1 &, d=1 \\ 3 &, d=2 \\ 2\varphi(d) &, 2 < d\mid 2^{k-2} \end{cases}</math>


{{同余理论}}