文章目录

• 定义
• 性质
• 求原根
• 应用
• • 1.指标
  • 2.NTT

在很多地方都用到了原根，比如 NTT 用到了原根的性质，比如离散对数需要用到的指标也与原根有关。

然而在此之前我对原根并不是非常了解，所以来补一补知识盲区。

定义

称 $g$ 为 $p$ 的原根，当且仅当 $g$ 在 $modp$ 意义下的阶为 $\phi (p)$ （这里的 $\phi (p)$ 是欧拉函数）。

p.s. 若 $g,p$ 互质， $n$ 是满足 gn≡1modmg^nequiv 1mod mgn≡1modm 的最小正整数 ， 称 $n$ 为 $g$ 模 $p$ 的阶。

性质

根据定义，有

∀i,j∈[0,φ(p)−1],i≠j,gi≢gjmodpforall i,jin[0,varphi(p)-1],ineq j,g^inotequiv g^jmod p∀i,j∈[0,φ(p)−1],i​=j,gi​≡gjmodp

证明很显然，可以用反证法：

若 $g$ 是 $p$ 的原根，且 ∃i,j∈[0,φ(p)−1],i≠j,gi≡gjmodpexist i,jin[0,varphi(p)-1],ineq j,g^iequiv g^jmod p∃i,j∈[0,φ(p)−1],i​=j,gi≡gjmodp

那么 g∣i−j∣≡1modpg^{|i-j|}equiv 1mod pg∣i−j∣≡1modp

因为 $i,j\in [0,\phi (p)-1],i\ne j$

所以 $0<|i-j|<\phi (p)-1$

由性质可知 $g$ 不是 $p$ 的原根。

求原根

做法：

还是利用原根的定义。

将欧拉函数质因数分解 φ(p)=∏pikivarphi(p)=prod p_i^{k_i}φ(p)=∏piki​​

若一个数 $g$ 满足 ∀i,gφ(p)pi≠1modpforall i,g^{frac{varphi(p)}{p_i}}neq 1mod p∀i,gpi​φ(p)​​=1modp ，那么他是 $p$ 的一个原根。

证明：

证明用到裴蜀定理。

假设存在一个 $k<\phi (p)$ 使得 gk≡1(modp)g^kequiv 1(mod;p)gk≡1(modp)

根据裴蜀定理，一定存在一组 $a,b$ 满足 $a\cdot k-b\cdot \phi (p)=gcd(k,\phi (p))$

所以 gk≡ggcd(k,φ(p))+b⋅φ(p)≡ggcd(k,φ(p))≡1(modp)g^kequiv g^{gcd(k, varphi(p))+bcdotvarphi(p)}equiv g^{gcd(k,varphi(p))}equiv 1(mod ; p)gk≡ggcd(k,φ(p))+b⋅φ(p)≡ggcd(k,φ(p))≡1(modp)

因为 $k<\phi (p)$ 所以 $gcd(k,\phi (p))<\phi (p)$

又因为 $gcd(k,\phi (p))|\phi (p)$

所以一定存在一个 gφ(p)pi≡1(modp)g^{frac{varphi(p)}{p_i}}equiv 1(mod; p)gpi​φ(p)​≡1(modp) ，通过检验这些数就可以知道一个数是不是原根了。

应用

1.指标

指标函数 $I(x)$ 定义如下：

gI(x)≡xmodpg^{I(x)}equiv xmod pgI(x)≡xmodp

可以对比一下连续的对数：

alog⁡ax=xa^{log_ax}=xaloga​x=x

可以发现两者非常相似。 $I(x)$ 也就是离散对数。与一般意义下的对数性质也非常相似，可以在取模意义下把乘法变成加法，把乘方变成乘法。

详情请见 [SDOI2015]序列统计 。

2.NTT

NTT 用原根来代替实数中使用的单位根 $\omega$ 。

设$g$是质数$p$的原根，再设ωn=g(p−1)/nomega_n=g^{(p-1)/n}ωn​=g(p−1)/n（$p$满足$n|p-1$）。

1. ωnn≡1(modp)omega_n^{n}equiv 1(mod; p)ωnn​≡1(modp)
2. ωn0,ωn1,…,ωnn−1omega_n^0,omega_n^{1},dots,omega_n^{n-1}ωn0​,ωn1​,…,ωnn−1​ 在 $modp$ 意义下互不相同
3. ωnk≡−ωnk+n/2omega_n^kequiv -omega_n^{k+n/2}ωnk​≡−ωnk+n/2​即ωnn/2≡−1(modp)omega_n^{n/2}equiv-1(mod; p)ωnn/2​≡−1(modp)

第 2 点保证了能够插值，第 3 条保证了 INTT（不知道是不是这么叫，反正就是类似 IDFT 的过程）的进行。