原根

阶

若 (a,m)=1 ，使 a^l \equiv 1 \pmod m 成立的最小的 l ，称为 a 关于模 m 的阶，记为 \text{ord}_ma 。

若 \text{ord}_ma=l ，则 \text{ord}_m{a^t} = \frac{l}{(t,l)}

由欧拉定理，设 \text{ord}_ma=l ，则 a^n \equiv 1 \pmod m 当且仅当 l | n ，特别地， l | \varphi(m) 。

  • 设 p 是素数， \text{ord}_pa=l ，那么有且仅有 \varphi(l) 个关于模 p 的阶为 l 且两两互不同余的数。
  • 设 \text{ord}_ma=l ，则 1, a, a^2, \cdots, a^{l-1} 关于模 m 两两互不同余。
  • 设 p 是素数， l|p-1 ，则存在 \varphi(l) 个关于模 p 的阶为 l 且两两互不同余的数。
  • 若 m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} ，则 \text{ord}_ma = [\text{ord}_{p_1}^{a_1}, \text{ord}_{p_2}^{a_2}, \cdots, \text{ord}_{p_k}^{a_k}]

原根

(g, m)=1 ，若 \text{ord}_mg = \varphi(m) ，则称 g 为 m 的一个原根。

g 为 m 的一个原根当且仅当 \{g, g^2, \cdots, g^{\varphi(m)}\} 构成模 m 的一个既约剩余系。

判断是否有原根

若 m 有原根，则 m 一定是下列形式： 2, 4, p^a, 2p^a 。这里 p 为奇素数， a 为正整数。

求所有原根

设 g 为 m 的一个原根，则集合 S = \{g^s | 1 \leq s \leq \varphi(m), (s, \varphi(m)) = 1\} 给出 m 的全部原根。因此，若 m 有原根，则 m 有 \varphi(\varphi(m)) 个关于模 m 两两互不同余的原根。

求一个原根

对 p-1 进行质因数分解得到不同的质因子 d_{1},d_{2},\ldots,d_{m} ，对于任意的 1<a<p ，要判定 a 是否是模 p 的原根，只需要检验 a^{\frac{p-1}{d_{1}}},a^{\frac{p-1}{d_{2}}},\ldots,a^{\frac{p-1}{d_{m}}} 这 m 个数中是否存在一个数在模 p 意义下与 1 同余。若存在，则 a 不是 p 的原根；若不存在，则 a 是 p 的原根。

另一种表达形式：

(g,m) =1 ，设 p_1, p_2, \cdots, p_k 是 \varphi(m) 的所有不同的素因数，则 g 是 m 的原根，当且仅当对任意 1 \leq i \leq k ，都有 g^{\frac{\varphi(m)}{p_i}} \not\equiv 1 \pmod m

证明

假设存在一个 t<\varphi(p)=p-1 使得 a^t\equiv 1\pmod{p} 且 \forall i\in\left[1,m\right]:a^{\frac{p-1}{d_{i}}}\not\equiv 1\pmod{p} 。

由裴蜀定理得，一定存在一组 k,x 满足 kt=x(p-1)+\gcd(t,p-1) ；由欧拉定理/费马小定理得 a^{p-1}\equiv 1\pmod{p} ；故有：

1\equiv a^{kt}\equiv a^{x(p-1)+\gcd(t,p-1)}\equiv a^{\gcd(t,p-1)}\pmod{p}

又有 t<p-1 ，故 \gcd(t,p-1)\leqslant t<p-1 。

又 \gcd(t,p-1)\mid(p-1) ，故 \gcd(t,p-1) 必至少整除 a^{\frac{p-1}{d_{1}}},a^{\frac{p-1}{d_{2}}},\ldots,a^{\frac{p-1}{d_{m}}} 中的至少一个，设 \gcd(t,p-1)\mid a^{\frac{p-1}{d_{i}}} ，则 a^{\frac{p-1}{d_{i}}}\equiv a^{\gcd(t,p-1)}\equiv 1\pmod{p} 。

故假设不成立。

用途

我们发现原根 g 拥有所有 DFT 所需的单位根 \omega 的性质，于是我们用 g^{\frac{p-1}{n}}\bmod{p} 来代替 \omega_{n} ，理论上就能把复数对应到一个整数，在模 p 意义下进行快速变换了。

但实际上由于快速傅里叶变换（FFT）实现的多项式乘法的过程中要求序列长度是 2 的幂次，因此这里模数 p 还需要保证 p-1 的标准分解式中素因子 2 的幂次足够大，参见 快速数论变换 ，

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论