前言：

原根和指标在数论中有大量的性质和规律，这里无法一一列举，只能简要写写用到的概率大一些的内容。本文是博主在复习时总结用，许多证明都已经略去，不建议初学者参考（速食主义者除外）。
主要包括：原根的定义及基本性质，求法，指标的定义，以及指标的基本应用。

原根

定义及性质：

要说明原根的完整定义，又要扯到阶那一块，这里就直接用一句话大致表示了： 若a" role="presentation" style="position: relative;">a$a$为模m的原根
那么必然满足(a,m)=1" role="presentation" style="position: relative;">(a,m)=1$(a,m)=1$且aφ(m)≡1 (mod m)" role="presentation" style="position: relative;">aφ(m)≡1 (mod m)$a^{\phi (m)}\equiv 1(modm)$，并且不存在一个正整数l<φ(m)" role="presentation" style="position: relative;">l<φ(m)$l<\phi (m)$，使得al≡1(mod m)" role="presentation" style="position: relative;">al≡1(mod m)$a^l\equiv 1(modm)$ 下面给出一些原根的基本性质（证明略）

性质1：设g为模m的原根，那么其充要条件是{g,g2,g3,……gφ(m)}" role="presentation" style="position: relative;">{g,g2,g3,……gφ(m)}$\{g,g^2,g^3,\dots \dots g^{\phi (m)}\}$组成模m的一个既约剩余系。

.

性质2：若m有原根，其必然满足：m=2,4,pα,2∗pα" role="presentation" style="position: relative;">pα,2∗pα$p^{\alpha },2\ast p^{\alpha }$，否则没有原根

.

性质3：若m有原根，那么其恰好有φ(φ(m))" role="presentation" style="position: relative;">φ(φ(m))$\phi (\phi (m))$个在模m意义下不同的原根。

这三条是原根最常用的性质，也是后面需要用到的。

原根求法：

对于一个存在原根的数m，其最小原根一般都不大，所以求m的最小原根的复杂度会很玄学（非常小）。。但如果要求所有原根，那复杂度就是妥妥的O(mlogm)了。 其实数论中并没有直接求原根的方式，但有快速检验是否为原根的方式。 将φ(m)" role="presentation" style="position: relative;">φ(m)$\phi (m)$因数分解，即φ(m)=p1k1p2k2……pnkn" role="presentation" style="position: relative;">φ(m)=pk11pk22……pknn$\phi (m)=p_1^{k_1}{p}_2^{k_2}\dots \dots p_n^{k_n}$如果一个数g" role="presentation" style="position: relative;">g$g$是模m的原根，则其必然满足对于任意一个1≤i≤n" role="presentation" style="position: relative;">1≤i≤n$1\le i\le n$，gφ(m)pi≠1(mod m)" role="presentation" style="position: relative;">gφ(m)pi≠1(mod m)$g^{\frac{\phi (m)}{p_i}}\ne 1(modm)$
所以一次check的复杂度就是φ(m)" role="presentation" style="position: relative;">φ(m)$\phi (m)$的质因子个数*快速幂复杂度。 然后根据目标强行枚举就可以了。

指标（离散对数）

根据原根的性质1，g1,g2,g3……gφ(m)" role="presentation" style="position: relative;">g1,g2,g3……gφ(m)$g^1,g^2,g^3\dots \dots g^{\phi (m)}$组成模m的一个既约剩余系。
指标用I" role="presentation" style="position: relative;">I$I$表示，满足：I(gx)=x" role="presentation" style="position: relative;">I(gx)=x$I(g^x)=x$（这个定义和对数函数非常类似，所以指标又称作离散对数） 并且，它与对数函数也有许多共同的性质：
I(ab)=I(a)+I(b)" role="presentation" style="position: relative;">I(ab)=I(a)+I(b)$I(ab)=I(a)+I(b)$
I(ak)=k×I(a)" role="presentation" style="position: relative;">I(ak)=k×I(a)$I(a^k)=k\times I(a)$
证明非常简单
gI(ab)≡ab≡gI(a)∗gI(b)≡gI(a)+I(b)(mod m)" role="presentation" style="position: relative;">gI(ab)≡ab≡gI(a)∗gI(