zl程序教程

您现在的位置是:首页 >  其它

当前栏目

求原根

2023-09-27 14:27:45 时间

原根

为了简单起见,只考虑素数的情况。(并不是只有素数才有原根

定义:对于素数 $p$,如果存在一个正整数 $1<a<p$,使得 $a^1, a^2, ..., a^{p-1}$ 模 $p$ 的值取遍 $1,2,...,p-1$ 的所有整数,称 $a$ 是 $p$ 的一个原根(primitive root),其实就是循环群的生成元。

如果 $a^j \equiv a^i(mod \ p)$,则 $i \equiv j(mod \ {p-1})$。这里有两个例子:

  • 3是7的原根,因为3-->2-->6-->4-->5-->1,然后开始循环
  • 2不是7的原根,因为2-->4-->1-->2-->4...,过早的循环了

注意到 $a^{p-1} \equiv 1(mod \ p)$,这个生成序列一定会包含1,且在此之前不会有循环——要是在出现1之前就循环了,就永远不会出现1了。

也就是说,原根的循环节为 $p-1$,非原根有较小的循环节,且是 $p-1$ 的约数(因为元素的阶整除群的阶)。

这就是判断原根的方法:枚举小循环长度$b$ (它一定是 $p-1$ 的真因子),判断是否有 $m^b \equiv 1(mod \ p)$(如果是,则表示 $m$ 不是原根)。虽然这个方法理论上并不是很优秀,但在算法竞赛中已经够用。

通俗地说,如果是原根,群的阶次方才为1;如果不是原根,群的阶的约数次方就会出现1.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll qpow(ll a, ll b, ll p) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % p;
    a = a * a % p, b >>= 1;
  }
  return res;
}

ll generator(ll p) {
  vector<ll> fact;
  ll phi = p - 1, n = phi;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      fact.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) fact.push_back(n);
  for (ll res = 2; res <= p; ++res) {
    bool ok = true;
    for (ll factor : fact) {
      if (qpow(res, phi / factor, p) == 1) {
        ok = false;
        break;
      }
    }
    if (ok) return res;
  }
  return -1;
}

int main()
{
    printf("%d\n", generator(998244353));
}

值得注意的是,原根并不是唯一的。

有结论:设群 $G=(a)$,若 $|G|=n$,则 $G=(a^r)$ 当且仅当 $(r, n)=1$,即生成元有 $\varphi (n)$ 个。

在上文中,群为 ${1, 2, ..., p-1}$ 模 $p$ 的乘法群。

例如,$p=7$ 时,3为原根,(5, 6)=1,所以 3^5 %7=5 也是原根。

 

 

参考链接:https://oi-wiki.org/math/primitive-root/