模意义下的指数问题

模意义下的指数问题

模乘法群描述可逆剩余类的乘法结构；
阶、原根、离散对数与二次剩余则研究幂在这一结构中的规律。

1 从模乘法到指数结构

模意义下的加法和乘法可以不断取模，但指数运算还会表现出周期、生成与求逆等更深的结构。

本章主线：剩余系 → 模乘法群 → 欧拉定理与指数降幂 → 元素的阶 → 原根 → 离散对数 → 二次剩余。

这些内容共同研究方程 ax≡b(modm)a^x\equiv b\pmod m：有时需要计算一个巨大指数，有时需要寻找未知指数，有时则要求解模意义下的平方根。

2 剩余系与模乘法群

2.1 完全剩余系

模 mm 的每个剩余类中各取一个代表元，得到的集合称为模 mm 的完全剩余系。

最常用的完全剩余系是 {0,1,2,…,m−1}\{0,1,2,\ldots,m-1\}。

若一个集合中任意两个元素模 mm 不同余，并且共有 mm 个元素，那么它就是模 mm 的完全剩余系。

2.2 既约剩余系

在完全剩余系中，只保留与 mm 互质的代表元，得到的集合称为模 mm 的既约剩余系。

例如，模 1010 的一个既约剩余系是 {1,3,7,9}\{1,3,7,9\}。

既约剩余系中的元素个数为欧拉函数 φ(m)\varphi(m)。

2.3 模乘法群

模 mm 的可逆剩余类在模乘法下构成阿贝尔群，记作 (Z/mZ)×(\mathbb Z/m\mathbb Z)^\times。

其中：

  • 元素是与 mm 互质的剩余类；
  • 运算是模 mm 乘法；
  • 单位元是 [1]m[1]_m；
  • 每个元素都存在乘法逆元；
  • 群的大小为 φ(m)\varphi(m)。
与代数结构的联系

这里的“群的阶”指群中元素的个数；后文“元素的阶”则指一个元素经过多少次幂回到单位元。

参见：02_代数运算结构

3 欧拉定理与指数降幂

3.1 欧拉函数回顾

若 m=∏i=1kpiai\displaystyle m=\prod_{i=1}^{k}p_i^{a_i}，则 φ(m)=m∏i=1k(1−1pi)\varphi(m)=m\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)。

欧拉函数的定义、质数幂公式与线性筛递推参见 03_数论函数与线性筛。

3.2 欧拉定理

若 gcd⁡(a,m)=1\gcd(a,m)=1，则 aφ(m)≡1(modm)a^{\varphi(m)}\equiv1\pmod m。

原因是：把既约剩余系中的每个元素都乘以 aa，取模后仍然得到同一个既约剩余系，只是顺序发生了变化。将所有元素相乘并约去原乘积，就得到欧拉定理。

因此，当 aa 与 mm 互质时，指数可以模 φ(m)\varphi(m)：ab≡a b mod φ(m)(modm)a^b\equiv a^{\,b\bmod\varphi(m)}\pmod m。

3.3 费马小定理

若 pp 是质数且 p∤ap\nmid a，则 φ(p)=p−1\varphi(p)=p-1，欧拉定理退化为 ap−1≡1(modp)a^{p-1}\equiv1\pmod p。

这就是费马小定理，也是模质数快速求逆元的依据。

3.4 扩展欧拉定理

当 aa 与 mm 不互质时，不能直接把指数对 φ(m)\varphi(m) 取模。

更一般地，对任意非负整数 bb 都有

ab≡{ab,b<φ(m),a b mod φ(m)+φ(m),b≥φ(m)(modm).a^b\equiv \begin{cases} a^b, & b<\varphi(m),\\ a^{\,b\bmod\varphi(m)+\varphi(m)}, & b\ge\varphi(m) \end{cases} \pmod m.

因此，处理十进制大指数时，不仅需要计算 b mod φ(m)b\bmod\varphi(m)，还要判断原指数是否已经达到 φ(m)\varphi(m)。

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
32
// 扩展欧拉定理：大指数降幂
ll mul( ll a, ll b, ll mod ) { /*模板代码略*/ }
ll qpow( ll a, ll k, ll mod ) { /*模板代码略*/ }

ll phi( ll n ) {
    ll res = n;
    for( ll i = 2; i * i <= n; ++ i ) {
        if( n % i == 0 ) {
            res = res / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    }
    if( n > 1 ) res = res / n * ( n - 1 );
    return res;
}

ll depow( const string &s, ll ph ) {
    ll res = 0;
    bool big = false;
    for( char ch : s ) {
        res = res * 10 + ch - '0';
        if( res >= ph ) big = true, res %= ph;
    }
    return big ? res + ph : res;
}

// 求 a^b mod mod，其中 b 为十进制字符串
ll solve( ll a, const string &b, ll mod ) {
    ll ph = phi( mod );
    ll k = depow( b, ph );
    return qpow( a, k, mod );
}

4 阶与原根

4.1 元素的阶

设 gcd⁡(a,m)=1\gcd(a,m)=1。满足 ak≡1(modm)a^k\equiv1\pmod m 的最小正整数 kk，称为 aa 模 mm 的阶，记作 ord⁡m(a)\operatorname{ord}_m(a)。

若 an≡1(modm)a^n\equiv1\pmod m，则 ord⁡m(a)∣n\operatorname{ord}_m(a)\mid n。

结合欧拉定理，可以得到

ord⁡m(a)∣φ(m).\operatorname{ord}_m(a)\mid\varphi(m).

因此，a0,a1,…,aord⁡m(a)−1a^0,a^1,\ldots,a^{\operatorname{ord}_m(a)-1} 模 mm 两两不同，而之后的幂按这一长度循环。

4.2 原根

若 ord⁡m(g)=φ(m)\operatorname{ord}_m(g)=\varphi(m)，则称 gg 为模 mm 的原根。

此时

1,g,g2,…,gφ(m)−11,g,g^2,\ldots,g^{\varphi(m)-1}

恰好遍历整个模 mm 既约剩余系。

从群论角度看，原根就是模乘法群的生成元。模 mm 存在原根，等价于 (Z/mZ)×(\mathbb Z/m\mathbb Z)^\times 是循环群。

4.3 原根的存在与判定

对 m≥2m\ge2，模 mm 存在原根，当且仅当

m=2, 4, pk, 2pk,m=2,\ 4,\ p^k,\ 2p^k,

其中 pp 是奇质数，kk 是正整数。

若模 mm 存在原根，则 gg 是原根，当且仅当对 φ(m)\varphi(m) 的每个不同质因数 qq 都有

gφ(m)/q≢1(modm).g^{\varphi(m)/q}\not\equiv1\pmod m.

因此，只需要分解 φ(m)\varphi(m)，从小到大枚举 gg 即可寻找最小原根。

若原根存在，其总数为 φ(φ(m))\varphi(\varphi(m))。

4.4 最小原根

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 原根：判定存在性 / 最小原根 / 所有原根
ll mul( ll a, ll b, ll mod ) { /*模板代码略*/ }
ll qpow( ll a, ll k, ll mod ) { /*模板代码略*/ }

ll phi( ll n ) {
    ll res = n;
    for( ll i = 2; i * i <= n; ++ i ) {
        if( n % i == 0 ) {
            res = res / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    }
    if( n > 1 ) res = res / n * ( n - 1 );
    return res;
}

// 原根存在当且仅当 n = 2, 4, p^k, 2p^k，p 为奇素数
bool exist( ll n ) {
    if( n == 2 || n == 4 ) return true;
    if( n < 2 ) return false;
    if( n % 2 == 0 ) n /= 2;
    if( n % 2 == 0 ) return false;
    for( ll p = 2; p * p <= n; ++ p ) {
        if( n % p == 0 ) {
            while( n % p == 0 ) n /= p;
            return n == 1;
        }
    }
    return true;
}

vector<ll> factor_phi( ll n ) {
    vector<ll> fac;
    for( ll p = 2; p * p <= n; ++ p ) {
        if( n % p == 0 ) {
            fac.push_back( p );
            while( n % p == 0 ) n /= p;
        }
    }
    if( n > 1 ) fac.push_back( n );
    return fac;
}

// 不存在返回 -1
ll min_root( ll n ) {
    if( !exist( n ) ) return -1;
    if( n == 2 ) return 1;
    if( n == 4 ) return 3;
    ll ph = phi( n );
    vector<ll> fac = factor_phi( ph );
    for( ll g = 2; g < n; ++ g ) {
        if( gcd( g, n ) != 1 ) continue;
        bool ok = true;
        for( ll p : fac ) {
            if( qpow( g, ph / p, n ) == 1 ) { ok = false; break; }
        }
        if( ok ) return g;
    }
    return -1;
}

vector<ll> all_roots( ll n ) {
    ll g0 = min_root( n );
    if( g0 == -1 ) return { };
    ll ph = phi( n ), cur = 1;
    vector<ll> roots;
    for( ll k = 1; k <= ph; ++ k ) {
        cur = mul( cur, g0, n );
        if( gcd( k, ph ) == 1 ) roots.push_back( cur );
    }
    sort( roots.begin( ), roots.end( ) );
    return roots;
}

5 离散对数

5.1 问题形式

离散对数问题要求解

ax≡b(modm)a^x\equiv b\pmod m

中的最小非负整数 xx。

它与实数中的对数类似，但模意义下的幂具有周期，普通的取对数方法无法使用。

当 gg 是模 mm 的原根时，每个可逆剩余类都可以唯一写成 gxg^x，于是模乘法可以转化为指数上的模加法。

5.2 BSGS

当 gcd⁡(a,m)=1\gcd(a,m)=1 时，可以使用 Baby-Step Giant-Step 算法。

取 t=⌈m⌉t=\lceil\sqrt m\rceil，将未知指数写成 x=it−jx=it-j，其中 0≤j<t0\le j<t。

原方程转化为

ait≡baj(modm).a^{it}\equiv ba^j\pmod m.

先枚举小步 jj，把 bajba^j 存入哈希表；再枚举大步 ii，寻找 (at)i(a^t)^i 是否出现过。

时间复杂度和空间复杂度均为 O(m)O(\sqrt m)。

5.3 ExBSGS

若 gcd⁡(a,m)≠1\gcd(a,m)\ne1，普通 BSGS 不能直接使用。

设 d=gcd⁡(a,m)d=\gcd(a,m)。若 d∤bd\nmid b，方程无解；否则可以同时约去一个 dd，并记录左侧被提取出来的系数。

不断重复这一过程，直到底数与新模数互质，再转化为普通 BSGS。

5.4 实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// BSGS / ExBSGS：求 a^x = b (mod mod)
ll mul( ll a, ll b, ll mod ) { /*模板代码略*/ }
ll qpow( ll a, ll k, ll mod ) { /*模板代码略*/ }

ll exgcd( ll a, ll b, ll &x, ll &y ) { /*模板代码略*/ }

ll inv( ll a, ll mod ) {
    ll x, y; 
    ll d = exgcd( a, mod, x, y );
    if( d != 1 ) return -1;
    return ( x % mod + mod ) % mod;
}

// 要求 gcd( a, mod ) = 1
ll bsgs( ll A, ll B, ll mod ) {
    A %= mod, B %= mod;
    if( mod == 1 || B == 1 ) return 0;
    if( A == 0 ) return B == 0 ? 1 : -1;
    int t = ceil( sqrt( mod ) );
    unordered_map<ll, ll> mp;
    ll cur = B;
    for( ll j = 0; j < t; ++ j ) {
        mp[cur] = j;
        cur = mul( cur, A, mod );
    }
    ll At = qpow( A, t, mod );
    cur = At;
    for( ll i = 1; i <= t + 1; ++ i ) {
        if( mp.count( cur ) ) return 1 * i * t - mp[cur];
        cur = mul( cur, At, mod );
    }
    return -1;
}

// 不要求 gcd( a, mod ) = 1
ll exbsgs( ll A, ll B, ll mod ) {
    A %= mod, B %= mod;
    if( B == 1 || mod == 1 ) return 0;
    if( A == 0 ) return B == 0 ? 1 : -1;
    ll k = 0, C = 1, d;
    while( ( d = gcd( A, mod ) ) > 1 ) {
        if( B % d != 0 ) return -1;
        k ++, B /= d, mod /= d;
        C = mul( C, A / d, mod );
        if( C == B ) return k;
    }
    ll t = ceil( sqrt( mod ) );
    unordered_map<ll, ll> mp;
    ll cur = B;
    for( ll j = 0; j < t; ++ j ) {
        mp[cur] = j;
        cur = mul( cur, A, mod );
    }
    ll At = qpow( A, t, mod );
    cur = mul( C, At, mod );
    for( ll i = 1; i <= t; ++ i ) {
        if( mp.count( cur ) ) return i * t - mp[cur] + k;
        cur = mul( cur, At, mod );
    }
    return -1;
}

6 二次剩余与 Cipolla

6.1 二次剩余

设 pp 为奇质数。若同余方程

x2≡n(modp)x^2\equiv n\pmod p

存在解，则称 nn 是模 pp 的二次剩余；否则称为二次非剩余。

当 n≢0(modp)n\not\equiv0\pmod p 时，欧拉判别准则给出

n(p−1)/2≡{1(modp),n 是二次剩余,−1(modp),n 是二次非剩余.n^{(p-1)/2}\equiv \begin{cases} 1\pmod p, & n\text{ 是二次剩余},\\ -1\pmod p, & n\text{ 是二次非剩余}. \end{cases}

若 xx 是一个非零解，则另一个解是 p−xp-x。

6.2 Cipolla 的核心构造

Cipolla 算法随机选择一个 aa，使 w=a2−nw=a^2-n 是模 pp 的二次非剩余。

随后在扩域中引入满足 i2=wi^2=w 的元素，并计算

(a+i)(p+1)/2.(a+i)^{(p+1)/2}.

结果的实部就是原方程的一个平方根。

随机选取的 ww 约有一半是二次非剩余，因此通常只需要常数次尝试；主要复杂度来自扩域快速幂，为 O(log⁡p)O(\log p)。

6.3 实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Cipolla：解 x^2 = n (mod p)，p 为奇素数
ll P, w;
mt19937_64 rng( time(0) );

ll mul( ll a, ll b ) { 
    return (ll)( (i128)a * b % P ); 
}

ll qpow( ll a, ll k ) {
    ll res = 1 % P; a %= P;
    for( ; k; k >>= 1, a = mul( a, a ) )
        if( k & 1 ) res = mul( res, a );
    return res;
}

struct Comp { ll r, i; };

Comp mul( Comp a, Comp b ) {
    ll rr = ( mul( a.r, b.r ) + mul( mul( a.i, b.i ), w ) ) % P;
    ll ii = ( mul( a.r, b.i ) + mul( a.i, b.r ) ) % P;
    return Comp{ rr, ii };
}

Comp qpow( Comp a, ll k ) {
    Comp res = { 1, 0 };
    for( ; k; k >>= 1, a = mul( a, a ) )
        if( k & 1 ) res = mul( res, a );
    return res;
}

bool check( ll n ) {
    if( n == 0 ) return true;
    return qpow( n, ( P - 1 ) / 2 ) == 1;
}

// 无解返回 {-1,-1}
pair<ll, ll> cipolla( ll n, ll p ) {
    P = p, n = ( n % P + P ) % P;
    if( n == 0 ) return { 0, 0 };
    if( P == 2 ) return { n, n };
    if( !check( n ) ) return { -1, -1 };
    ll a;
    while( true ) {
        a = uniform_int_distribution<ll>( 0, P - 1 )( rng );
        w = ( mul( a, a ) - n + P ) % P;
        if( qpow( w, ( P - 1 ) / 2 ) == P - 1 ) break;
    }
    ll x = qpow( { a, 1 }, ( P + 1 ) / 2 ).r;
    ll y = ( P - x ) % P;
    if( x > y ) swap( x, y );
    return { x, y };
}

7 与后续内容的联系

  • 欧拉定理与扩展欧拉定理处理巨大指数取模；
  • 原根把循环模乘法群转化为指数上的加法结构；
  • BSGS 与 ExBSGS 求解模意义下的指数方程；
  • Cipolla 求解模质数下的平方根；
  • 原根与模逆元也是 NTT 等算法的重要基础。

相关内容：

数学 > 数论
#数论/模运算
模意义下的指数问题
http://miqiu.space/posts/cfff9083/
作者
Miqiu
发布于
2026年7月1日
许可协议