阶、原根、离散对数

本文中，若无特殊说明，$m$ 代表正整数，$p$ 代表质数。

事实上，在题目中我们大多数情况下都是讨论对质数取模的情况。

阶

定义

若 $(a,m)=1$，满足 $a^n = 1 \pmod m$ 的最小的 $n$ 称为 $a$ 模 $m$ 的阶，记作 $\delta_m a$。

如果 $(a,m)=1$ 不互质，那么不难发现，不存在 $n$，使得 $a^n = 1 \pmod m$，故我们不定义 $a$ 模 $m$ 的阶。

性质

本节中 $a,b$ 均与 $m$ 互质。

1. $a,a^2,\ldots,a^{\delta_m a}$ 模 $m$ 两两不同。

   【引理 1】完全剩余系中与 $m$ 互质的剩余类所构成的系称为缩系，缩系内四则运算均封闭。
   （证明略）

   性质 1 证明：
   用反证法，假设存在 $1\le i < j \le \delta_m a$，使得 $a^i \equiv a^j \pmod m$，因为 $a^i$ 和 $a^j$ 均与 $m$ 互质，存在逆元，故 $a ^{j-i} \equiv 1 \pmod m$，而 $j-i < \delta_m a$，故 $\delta_m a$ 不是最小，矛盾！

2. 若 $a^n \equiv 1 \pmod m \iff n\equiv 0\pmod {\delta_m a }$

   【引理 2】若 $a^x \equiv a^y \equiv 1 \pmod m$，则 $a^{\gcd(x,y)}\equiv 1 \pmod m$。
   【引理 2 证明】因为存在逆元，我们可知 $a^{Ax+By}\equiv 1 \pmod m\ (A,B\in\Z)$。由裴蜀定理，$\gcd(x,y)$ 能表示为 $x,y$ 的线性组合，故引理成立。

   性质 2 证明：
   先证 $\Leftarrow$：若 $n\equiv 0\pmod {\delta_m a }$，设 $n=k\delta_m a\ (k\in \N^{*})$，$a^n = \left(a^{\delta_m a}\right)^{k}\equiv 1\pmod m$ 。
   再证 $\Rightarrow$：用反证法，假设存在 $a^n \equiv 1$ 且 $n$ 不是 $\delta_m a$ 的倍数，则 $\gcd(n,\delta_m a)$，由引理 2 可知 $a^{\gcd(n,\delta_m a)}\equiv 1 \pmod m$，故 $\delta_m a$ 不是最小，矛盾！

3. $a^x\equiv a^y \pmod m \iff x \equiv y \pmod {\delta_m a}$。

   性质 3 证明：
   先证 $\Leftarrow$：若 $x \equiv y \pmod {\delta_m a}$，则 $a^{x-y} \equiv 1 \pmod m$，则 $a^x \equiv a^y \pmod m$。
   再证 $\Rightarrow$：因为 $a^{x-y}\equiv 1\pmod m$，由性质 2 可知，$x-y$ 为 $\delta_m a$ 的倍数，故成立。

4. $\delta_m (ab) = \delta_m a \delta_m b \iff (\delta_m a,\delta_m b)=1$。

   性质 4 证明：

   • 先证 $\Rightarrow$：
     因为 $a^{\delta_m a}\equiv 1\pmod m$，$b^{\delta_m b}\equiv 1\pmod m$，故 $ab^{[\delta_m a,\delta_m b]}\equiv 1\pmod m$
     由性质 2 可知，$\delta_m(ab)\mid [\delta_m a,\delta_m b]$，即 $\delta_m a \delta_m b \mid [\delta_m a,\delta_m b]$。
     故 $(\delta_m a,\delta_m b)=1$。

   • 再证 $\Leftarrow$：
     因为 $a^{\delta_m a}\equiv 1\pmod m$，$b^{\delta_m b}\equiv 1\pmod m$，故 $ab^{\delta_m a\delta_m b}\equiv 1\pmod m$，即 $\delta_m a\delta_m b\mid \delta_m(ab)\ (*)$。

     又 $1\equiv(ab)^{\delta_m(ab)\delta_m b}\equiv(a)^{\delta_m(ab)\delta_m b}\pmod m$，可知 $\delta_m a \mid \delta_m(ab)\delta_m b$。
     结合 $(\delta_m a,\delta_m b)=1$，得 $\delta_m a \mid \delta_m(ab)$。
     同理 $\delta_m b \mid \delta_m(ab)$，故 $\delta_m a\delta_m b \mid \delta_m(ab)\ (\triangle)$。

     由 $(*),(\triangle)$ 两式得 $\delta_m (ab) = \delta_m a \delta_m b$。

5. $\delta _m(a^k) = \dfrac{\delta_m a}{(\delta_m a,k)}$。

   性质 5 证明：
   设 $\delta _m(a^k)=d$，有 $\left(a^k\right)^d\equiv 1\pmod m$。
   即要找到最小的 $d$ 满足 $a^{kd}\equiv 1\pmod m$。
   由性质 2 可知，我们需要让 $kd \equiv 0\pmod {\delta_m a }$。
   不难发现最小的 $d$ 即为 $\dfrac{\delta_m a}{(\delta_m a,k)}$。

求法

如果求 $a$ 的阶（$a$ 与 $m$ 互质），初始令阶 $x$ 为 $\varphi(m)$，对 $\varphi(m)$ 的每一个质因数，如果除了它之后仍然有 $a^x \equiv 1 \pmod m$，则不断除掉这个质因数，最后得到的就是它的阶。

正确性说明：
假设最后结果为 $d$。

显然有 $a^d\equiv 1\pmod m$，只需证明不存在更小的 $x$ 使得 $a^x\equiv 1\pmod m$ 即可。
如果 $\delta_m a\ne d$，则存在 $f\mid d$，$a^{d/f}\equiv 1\pmod m$，显然与我们的算法矛盾，故该算法能正确求出阶。

复杂度 $O(\sqrt m +\log^2 m)$。（预处理质因数 $\sqrt m$，有 $\log m$ 个质因数，每次快速幂判断复杂度为 $\log m$）.

参考代码：

ll ord = phi(m);
for(auto f:fp)while(ord%f==0 && ksm(a,ord/f,m)==1)ord/=f;

其中 fp 是存有 $\varphi(m)$ 的质因数的 vector，函数 ksm(a,b,p) 表示 $a^b \bmod m$ 的值。

原根

原根和阶是紧密相关的概念。

定义

若 $\delta_m(g) = \varphi(m)$，称 $g$ 为模 $m$ 的原根。

性质

1. （原根判定定理）$g \text{ 是 } m \text{的原根} \iff \forall p \mid \varphi(m),g^{\frac{\varphi(m)}{g}}\not \equiv 1 \pmod m \text{ 且 } (g,m)=1$。

   证明：
   与阶的求法正确性等价，读者自证不难。

2. （原根个数定理）若 $m$ 存在一个原根 $g$，则所有原根可以表示为 $g^k$，其中 $(k,\varphi(m))=1$。故原根个数有 $\varphi(\varphi(m))$个。

   证明：
   运用阶的性质 5 易证，留作读者练习。

3. （原根存在定理）$m$ 存在原根当且仅当 $m=2,4$ 或 $m=p^\alpha, 2p^\alpha$，其中
   $p$ 为质数，$\alpha\in \N^*$。

4. 若一个质数 $p$ 存在原根，其最小原根 $g_{\text{min}}=O(p^{1/4})$。（这并不意味着存在一个小于等于 $p^{1/4}$ 的原根）

求法

1. 判断原根是否存在；$O\left(\sqrt n\right)$ （或预处理 $O(n)$）
2. 若存在，从 $1$ 开始枚举与 $n$ 互质的数，找到最小原根；$O\left(n^{0.25} \log^2 n\right)$
3. 找出所有与 $\varphi(n)$ 互质的 $k$，求出所有原根。$O(\varphi(n)\log\varphi(n))$
4. （对所有原根排序. $O(\varphi(\varphi(n))\log\varphi(\varphi(n)))$。

参考代码：

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

using ll=long long;
inline int read(){int f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}

const int N = 1e6+5;
bool vis[N];
int pri[N],cnt,phi[N];
bool have[N];

int ksm(int a,int b,int p){
    int r = 1;
    while(b){
        if(b&1)r=(ll)r*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return r;
}

int main(){
    // 线性筛预处理出素数和欧拉函数
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])pri[cnt++]=i,phi[i]=i-1;
        for(int j=0;j<cnt&&i*pri[j]<N;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    
    
    have[2]=have[4]=1; // 2,4
    for(int i=1;i<cnt;i++){
        for(ll j=pri[i];j<N;j*=pri[i])have[j]=1; // p^a
        for(ll j=2*pri[i];j<N;j*=pri[i])have[j]=1; // 2p^a
    }

    int T=read();
    while(T--){
        int n=read(),d=read();
        if(!have[n]){ // 没有原根
            puts("0\n");
            continue;
        }

        vector<int> fac; // 求出φ(n)的质因数
        int P = phi[n];
        for(int i=2;i*i<=P;i++){
            if(P%i==0){
                fac.push_back(i);
                while(P%i==0)P/=i;
            }
        }
        if(P!=1)fac.push_back(P);
        vector<int> g;
        for(int i=1;;i++){
            if(__gcd(n,i)!=1)continue; // i 与 n 互质
            bool ok = 1;
            for(auto p:fac)
                if(ksm(i,phi[n]/p,n)==1){ok=0;break;}

            if(ok){
                for(int k=1;k<=phi[n];k++)
                    // 找到所有原根
                    if(__gcd(k,phi[n])==1)g.push_back(ksm(i,k,n)); 
                break;
            }
        }
    
        sort(g.begin(),g.end());
        assert(g.size()==phi[phi[n]]);
        printf("%d\n",(int)g.size());
        for(int i=d-1;i<g.size();i+=d)printf("%d ",g[i]);
        puts("");
    }

    return 0;
}

离散对数

定义

当 $(a,m)=1$ 时，若存在 $a^k\equiv b\pmod m$，则将满足上式的最小自然数 $k$ 称作对 $m$ 取模下，以 $a$ 为底 $b$ 的离散对数，记作$\operatorname{ind} _a b = k$。

这就允许我们将模意义下的乘法化为加法，从而更方便的解决问题。

性质

1. $\operatorname{ind} _a 1 = 0$。
2. $\operatorname{ind} _a a = 1$。
3. $\operatorname{ind}_a (xy) = \operatorname{ind}_a x + \operatorname{ind}_a y \pmod {\delta_m a}$，$\operatorname{ind}_a x^n \equiv n \operatorname{ind}_a x \pmod {\delta_m a}$。
4. $x\equiv y \pmod m \iff \operatorname{ind}_a x = \operatorname{ind}_a y$。

注意：在取离散对数之后，取模变为 $\delta_m a$，而不是原来的 $m$。

求法

BSGS 算法：在 $O(\sqrt m)$ 的时间内求 $a^x=b\pmod m$ 的解。要求 $(a,m)=1$。

设 $t=\lceil\sqrt m\rceil$。不妨设解 $x=it-j$。（$0\le j \le t$）

则 $a^{it-j} \equiv b \pmod m$，即 $a^{it}\equiv ba^j \pmod m$。

求出 $i,j$ 后就能得到答案。（互质的原因是我们推导用到了逆元）

参考代码：

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
ll ksm(ll a,ll b,ll p){
    ll r=1;
    while(b){
        if(b&1)r=r*a%p;
        a=a*a%p;
        b>>=1;
    }
    return r;
}
int main(){
    ll p,a,b;
    scanf("%lld%lld%lld",&p,&a,&b);
    ll t=ceil(sqrt(p));
    map<ll,int>vis; 
    for(ll i=0,now=b;i<=t;i++,now=now*a%p)vis[now]=i;
    ll at = ksm(a,t,p);
    for(ll i=1,now=at;i<=t;i++,now=now*at%p){
        if(vis.count(now)){
            printf("%lld\n",i*t-vis[now]);
            return 0;
        }
    }
    puts("no solution");
    return 0;
}

习题

P6091 【模板】原根

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

[ABC335G] Discrete Logarithm Problems （参考代码）