抽象代数入门

本文主要梳理和原根有关的群论基础知识。

以后学的抽代知识也会往这里填。

2020.5.8：为了学二次剩余，又来补充内容了。

阶

阶（order）在群中有两个相关含义。一是指群的元素个数——这不是我们今天要讨论的。

群中一个元素$a$的阶（有时称为周期）是指使得$a^m=\varepsilon$的最小正整数$m$。$\varepsilon$是这个群的单位元。若不存在这样的$m$，称$a$有无限阶。有限群的所有元素均有有限阶。

一个元素$a$的阶被记为$\text{ord}(a)$或者$|a|$。

在剩余系（模意义）下的阶我们也记作$\text{ord}_pa$，表示$\bmod p$意义下$a$的阶。

原根

原根（primitive root）是数论（域论）中的概念。

对于两个正整数$a,m$，如果$a\perp m$，那么根据欧拉定理，有$a^{\varphi(m)}\equiv 1\pmod m$。

而如果在$\bmod m$意义下$a$的阶等于$\varphi(m)$，即$\text{ord}_ma=\varphi(m)$，则称$a$是$\bmod m$意义下的原根。此时，$a^0,a^1,\cdots,a^{\varphi(m)-1}$构成$m$的简化剩余系。

特殊地，当$m$是质数时，$\varphi(m)=m-1$，也就是说此时$a^0,a^1,\cdots,a^{\varphi(m)-1}$构成$m$的剩余系。

原根的存在性

并不是所有的$\bmod m$剩余系都有原根。

$\bmod m$有原根的充要条件是$m=2,4,p^n,2p^n$，其中$p$是奇素数，$n$是任意正整数。

如果 p 是一个奇素数且有原根$g$，那么$g$或者$g+p$是模$p^2$的一个原根。

如果 r 是模$p^2$的原根，那么它也是模$p^k$的原根。

原根的计算

考虑枚举$a$使得$a\perp m$。然后我们枚举$\varphi(m)$的质因子$p$，判断是否$a^{\frac{\varphi(m)}{p}}\equiv 1\pmod {m}$。如果该等式始终不成立，那么$a$就是原根。

该算法复杂度为$O(m\log_2m+\sqrt{\varphi(m)}+\varphi(m)\log \varphi(m)\log_2m)$。

如果$m$是质数那么复杂度就是$O(m+\sqrt{\varphi(m)}+\varphi(m)\log \varphi(m)\log_2m)$。

实际运行过程中原根都不会太大，因此该算法通常比较快。

int pw(int a,long long m,int P){
    int res=1;
    m%=(P-1);
    while(m)m&1?res=1ll*res*a%P:0,a=1ll*a*a%P,m>>=1;
    return res;
}
int primitive_root_prime(int p){
    vector<int> vd;
    int pp=p-1;
    for(int i=2;i*i<=pp;++i){
        if(pp%i)continue;
        vd.pb(i);
        while(pp%i==0)pp/=i;
    }
    if(pp>1)vd.pb(pp);
    pp=p-1;
    FOR(i,2,p-1){
        bool flag=0;
        for(auto d:vd){
            if(pw(i,pp/d,p)==1){flag=1;break;}
        }
        if(flag==0)return i;
    }
    assert(0); // prime must have primitive root
    return -1;
}

域

域（Field）是一种可以进行加减乘除（除了除以$0$，$0$即加法单位元）运算的代数结构。

非正式地说，域是一个集合且定义了加法和乘法运算。并且每个元素都有加法和乘法的逆元，使得能够定义除法和减法运算。

确切地说，它需要满足如下性质：

• 加法和乘法结合律；
• 加法和乘法交换律；
• 存在加法和乘法的单位元；
• 存在加法逆元；
• 存在乘法逆元；
• 有加法对乘法的分配律。

常见的域有：

• 有理数域$\mathbf{Q}$。
• 复数域$\mathbf{C}$。
• Constructible numbers：可以尺规作图构造的数字（长度、面积）集合。

参考文献

Wikipedia - Order (group theory))

Wikipedia - Field)