🔖 math数论原根

什么是原根

  • 原根的定义

    对于正整数 N，如果正整数 g 满足 gcd(g,N)=1 且 {g0,g1,⋯,gφ(N)−1} 两两模 N 不同余，则称 g 为 N 的一个原根。

    由于 gcd(A,B)=1 ⇔ gcd(AmodB,B)=1。所以，{g0,g1,⋯,gφ(N)−1} 构成 N 的一个既约剩余系。

  • 原根的阶

    如果正整数 X 和 N 互质，且 r 为使得 Xr≡1modN 成立的最小正整数，则称 r 为 X 模 N 的阶，记做 δN(X)=r.

    所以，原根的定义也可以描述为：X 是模 N 的一个原根的充要条件为 φ(N)=δN(X).

如何求原根

  • 【性质1】：r∣φ(N)

    由定义可知，φ(N)⩾δN(X)=r；不妨设 φ(N)=k⋅r+t，其中 0⩽t<r.
    因为 Xr≡1modN，所以有 Xφ(N)≡Xk⋅r+t≡Xt≡1modN.
    由于 δN(X)=r；所以，必有 t=0.
    故 r∣φ(N).

算法原理

枚举 X 是否 N 的原根即可。

通过【性质 1】，我们可以简单地通过检查所有的 {n|1<n<φ(N)且n∣φ(N)} 是否都满足 Xn≢1modN 来判断 X 是否为模 N 的一个原根。进一步地，如果 φ(N)=p1k1p2k2⋯psks，我们仅需检查 n=φ(N)pi,1⩽i⩽s 就够了。原因很简单，如果 ∀i,1⩽i⩽s 都有 0⩽ai⩽ki 成立，且 ∃j,1⩽j⩽s 使得 0⩽aj<kj 成立；则必有 p1a1p2a2⋯psas∣φ(N)pj 成立。所以，若 Xp1a1p2a2⋯psas≡1modN，那么 Xφ(N)pj≡1modN 也会成立。

综上，对于每个数 g，最多检查 φ(N) 的素因子个数次即可判断其是否为 N 的一个原根。

程序实现

primitive.root.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void calcFactor(int N, vector<int>& fac) {
  int sm = ceil(sqrt(1.0 * N));
  for (int i = 2; i <= sm; ++i) {
    if (N%i == 0) {
      fac.push_back(i);
      while (N%i == 0) N /= i;
    }
  }
  if (N > 1) fac.push_back(N);
}


int calcPrimitiveRoot(int N) {
  vector<int> fac;


  // phi(N) 返回 N 的欧拉函数值，实现略
  int PHI_N = phi(N);
  calcFactor(PHI_N, fac);


  for (int i = 0; i < fac.size(); ++i) fac[i] = PHI_N / fac[i];
  for (int g = 2; ; ++g) {
    bool flag = true;
    for (int i = 0; i < fac.size(); ++i) {
      // powerMod 返回 $g^{fac[i]} \mod N$，实现略
      if (powerMod(g, fac[i], N) == 1) {
        flag = false;
        break;
      }
    }
    if (flag) return g;
  }    
}

小记

  • 哪些数有原根

    N 有原根的充要条件是 N=2,4,pk,2×pk。其中，p 为奇素数，k 为任意正整数。

© 2017-2025 光和尘有花满渚、有酒盈瓯

Comments