阶

约 817 个字 101 行代码 预计阅读时间 4 分钟

定义

若 $p>1$，$gcd(a,p)=1$，则必有一个 $x$ 满足

$a^x\equiv 1 \pmod p$,

且 $x$ 为最小正整数解,

则 $x$ 为 $a$ 模 $p$ 的阶,记作 $\delta_p(a)$

性质

1. $a,a^2,...,a^{\delta_p(a)}$ 模 $p$ 两两不同余

2. 若 $a^n\equiv 1 \pmod p$，则$\delta_p(a) \mid n$

3. 若 $a^r \equiv a^t \pmod p$，则 $r\equiv t \pmod {\delta_p(a)}$

4. 若 $\gcd(a,p)=\gcd(b,p)=1$，则 $\delta_p(ab)=\delta_p(a)\delta_p(b)$ 的充分必要条件是 $\gcd\big(\delta_p(a),\delta_p(b)\big)=1$

5. 若 $\gcd(a,p)=1$，则$\delta_p(a^k)=\dfrac{\delta_p(a)}{\gcd\big(\delta_p(a),k\big)}$

原根

定义

$\delta_p(a)=φ(p)$

则 $a$ 为模 $p$ 的原根(Primitive Root)

原根存在定理

$p$ 能表示为下列形式之一：

$2,4,k^n,2*k^n$，其中 $k$ 为奇素数。

原根判定定理

若 $p>2$，$gcd(a,p)=1$或者$a^{φ(p)}\equiv 1 \pmod p$

前者用__gcd判断，后者用取模快速幂判断，根据luogu p6091，二者效率差别不大

则 $a$ 是模 $p$ 的原根的充要条件是，对于 $φ(p)$ 的每个素因数 $j$，都有 $a^{\frac{φ(p)}{j}}\not\equiv 1\pmod p$。

数量

$φ(φ(p))$

最多是 $p/2$

常见数的最小原根

2——1,4——3,998244353——3,1e9+7——5

求 p 的所有原根的步骤

1. 线性筛处理

不大于 $p$ 的素数，不大于 $p$ 的正整数的欧拉函数值，不大于 $p$ 的有原根的模数

1. 判断 $p$ 是否有原根

2. 求最小原根

用已经筛出的素数求 $φ(p)$ 的质因数,并顺便标记和 $φ(p)$ 互素的数

枚举 $i$ （从1开始）,满足 $gcd(i,n)=1$,

对于 $φ(p)$ 的每个质因数 $j$

如果 $i^{φ(p)/j}\equiv 1 \pmod p$

说明 $i$ 不是原根

继续循环，直到找到合适的 $i$ 为止

有人证明过，最多 $n^{1/4}$ 次就能找到最小原根

1. 求所有原根

枚举 $φ(p)$ 以内的正整数 $s$

如果 $s$ 与 $φ(p)$ 互质，则 $a^s$ 是一个原根

时间复杂度

$O(nlogloglogn)$

优化

如果要求顺序输出原根，基数排序比快速排序更快

typedef long long ll;
const int N=1e6+7;
int p[N],phi[N],factor[15];
bool v[N],pr[N],coprime[N],proot[N];
void init(int n)//筛素数，欧拉函数，有原根的数
{
    pr[2]=pr[4]=phi[1]=1;
    int cnt=0;
    for(int i=2;i<=n;++i)
    {
        if(!v[i])
        {
            p[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt && p[j]*i<=n;++j)
        {
            v[p[j]*i]=1;
            if(!(i%p[j]))
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*phi[p[j]];
        }
    }
    for(int i=1;i<cnt;++i)
    {
        for(ll j=p[i];j<=n;j*=p[i])
            pr[j]=1;
        for(ll j=2*p[i];j<=n;j*=p[i])
            pr[j]=1;
    }
}
long long fast_power(long long base,long long exponent,ll mod)
{
    long long result=1;
    for(;exponent>0;exponent>>=1)
    {
        if(exponent&1)
            result=result*base%mod;
        base=base*base%mod;
    }
    return result;
}
vector<int> PrimitiveRoot(int n)
{
    vector<int> vec;
    if(!pr[n])//模数n没有原根
        return vec;
    if(n==2 || n==4)
    {
        vec.push_back(n-1);
        return vec;
    }
    int temp=phi[n];
    int cnt=0;
    for(int i=0;p[i]*p[i]<=temp;++i)//求φ(n)的质因子，用埃氏筛的思想筛出与φ(n)互质的数(即coprime[i]=0)
    {
        if(!(temp%p[i]))
        {
            factor[cnt++]=p[i];
            while(!(temp%p[i]))
                temp/=p[i];
            for(int j=p[i];j<phi[n];j+=p[i])
                coprime[j]=1;
        }
    }
    if(temp>1)//处理大于根号φ(n)的质因子
    {
        factor[cnt++]=temp;
        for(int i=temp;i<phi[n];i+=temp)
            coprime[i]=1;
    }
    int minPr=1;
    for(;;++minPr)//求最小原根
    {
        for(;__gcd(minPr,n)!=1;++minPr);
        int j=0;
        for(;j<cnt && fast_power(minPr,phi[n]/factor[j],n)!=1;++j);
        if(j>=cnt)
            break;
    }
    temp=minPr;
    for(int i=1;i<phi[n];++i,temp=temp*minPr%n)//求所有原根
    {
        if(!coprime[i])
            proot[temp]=1;
        else
            coprime[i]=0;//清零
    }
    for(int i=1;i<n;++i)//排序原根
    {
        if(proot[i])
        {
            proot[i]=0;//清零
            vec.push_back(i);
        }
    }
    return vec;
}

原根应用

1. 乘法转化为加法

若 $p$ 有原根，

根据阶的性质1和原根的定义，

若 $g$ 是 $p$ 的原根，$1 \le k \le φ(p)$

$g^k \pmod p$ 能生成$[1, p-1]$ 中 $φ(p)$ 个数

换句话说就是

$g^1,g^2...g^{φ(p)} \pmod p$与 $[1,p-1]$ 中的数形成了单射

当 $p$ 是素数时，就形成了双射

把x比作萝卜，y比作坑：
单射就是一个萝卜一个坑，有的坑有可能没萝卜；
满射就是所有坑都有萝卜，有的坑可能有不止一个萝卜；
双射就是严格的一个萝卜一个坑，一个坑一个萝卜，所有萝卜都有坑，所有坑都有萝卜。

若 $p$ 是素数，$1 \le a,b$

则 $a*b=g^{Ind_ga+Ind_gb} \pmod p$

Ind是离散对数，在bsgs&exbsgs里会介绍

因此求出 $p$ 的原根 $g$，然后我们就可以把原序列 $a[i]$ 变成 $g^{b[i]}$ ，从而我们就把乘法变成了加法，即

$a[i]*a[j]=a[k] \pmod p$ 变成

$b[i]+b[j]=b[k] \pmod {p-1}$

要特判0,因为原根不会生成0

例题1 例题2

1. NTT，用最小原根的板子搞出原根来，才能做

参考博客1

参考博客2