阶、原根、离散对数

阶

定义

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

性质

$a,a^2,\ldots,a^{\delta_m a}$ 模 $m$ 两两不同。
若 $a^n \equiv 1 \pmod m \iff \delta_m a \mid n$
$a^p\equiv a^q \pmod m \iff p \equiv q \pmod {\delta_m a}$ 。
$\delta_m (ab) = \delta_m a \delta_m b \iff (\delta_m a,\delta_m b)=1$ 。
$\delta _m(a^k) = \dfrac{\delta_m a}{(\delta_m a,k)}$ 。
$\exists k, a^k = b \iff \delta_m b \mid \delta_m a$ 。（可用阶性质 5 证明）

求法

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

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

参考代码：

若已知：

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

ll a,p;
vector<ll> fp; // phi(p) 的因数

则 ord 就是 a 的阶。

ll ord = p-1;
for(auto f:fp){
    while(ord%f==0 && ksm(a,ord/f,p)==1)ord/=f;
}

原根

定义

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

性质

当 $m$ 为质数时， $g^i \bmod m (0<i<m)$ 的值互不相同，恰为 $1,2,\ldots,m-1$ 。（阶性质 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$ 。
（原根个数定理）若 $g$ 为 $m$ 的一个原根，则所有原根可以表示为 $g^k$ ，其中 $(k,\varphi(m))=1$ 。故原根个数有 $\varphi(\varphi(m))$ 个。
（原根存在定理） $m$ 存在原根当且仅当 $m=2,4$ 或 $m=p^\alpha, 2p^\alpha$ ，其中
$p$ 为质数， $\alpha\in \N^*$ 。
若一个数 $m$ 存在原根，其最小原根 $g=O(m^{1/4})$ 。

求法

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

离散对数

定义

设有原根的正整数 $m$ ，设其一个原根为 $g$ 。
对于 $(a,m)=1$ 的整数 $a$ 恰有一个 $k$ 使 $g^k\equiv a\pmod m$ ，记 $k=\operatorname{ind} _g a$ 。

性质

$\operatorname{ind} _g 1 = 0$ 。
$\operatorname{ind} _g g = 1$ 。
$\operatorname{ind} (ab) = \operatorname{ind} a + \operatorname{ind} b \pmod {\varphi(m)}$ ， $\operatorname{ind} a^n \equiv n \operatorname{ind} a \pmod {\varphi(m)}$ 。
$\operatorname{ind} _{g_1} a \equiv \operatorname{ind} _{g_1} {g_2} \operatorname{ind} _ {g_2} a \pmod {\varphi(m)}$ 。
$a\equiv b \pmod m \iff \operatorname{ind} a = \operatorname{ind} b$ 。

注意：在取离散对数之后，取模变为 $\varphi(m)$ ，而不是原来的 $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;
}