有限域结构定理

· · 题解

结构定理一： 设 F 是一个特征为素数 p 的有限域，则 F 中的元素个数为 p^n，n 是一个正整数。

证明： 由于 F 是一个特征为 p 的有限域，所以 F 的素子域与 \mathbb{Z}/p\mathbb{Z} 同构。因此 F 是 \mathbb{Z}/p\mathbb{Z} 的有限扩张，设扩张次数为 n，且 a_1,a_2,\cdots ，a_n 是 F 在 \mathbb{Z}/p\mathbb{Z} 上的一组基。则 F=\{b_1a_1+b_2a_2+\cdots+b_na_n\vert b_i\in \mathbb{Z}/p\mathbb{Z},i=1,2,\cdots,n\}，所以 F 中的元素个数为 p^n。

引理一： 如果 f(x) 在 F 上不可约，则 F[x]/\langle f(x)\rangle 是一个域。

证明： 模 f(x) 同余是 F[x] 上的一个等价关系。不难证明 F[x]/\langle f(x)\rangle 是个含幺交换环。

只要证明任意非 0 元有乘法逆元，设 r(x)\neq 0\in F[x]/\langle f(x)\rangle，则 0\le \operatorname{deg}(r(x))\lt\operatorname{deg}(f(x))，因为 f(x) 在 F 上不可约，所以 \gcd(f(x),r(x))=1，因此 r(x) 在 F[x]/\langle f(x)\rangle 中有乘法逆元。

引理二： 域 F 上任意一个次数 \ge 1 的多项式 f(x) 在 F 上都有分裂域。

证明： 对多项式次数 n 进行数学归纳：

任取 f(x) 的一个不可约因子 p(x)，定义 F_1=F[x]/\langle p(x)\rangle，则 F_1 是个域，且令 \alpha=x+\langle p(x)\rangle \in F_1，p(\alpha)=p(x)+\langle p(x)\rangle=0+\langle p(x)\rangle，所以 \alpha 是 p(x) 的根。

在域 F_1 上，将 f(x) 写为 (x-\alpha)\cdot g(x)，g(x)\in F_1。

此时 \operatorname{deg}(g(x))=n-1，根据归纳假设，g(x) 在 F_1 上存在分裂域 E。可以验证 E 是 f(x) 在 F 上的分裂域。

结构定理二（存在性）： 对于任何素数 p 和任意正整数 n， 总存在一个有限域恰好含有 p^n 个元素。

证明： 考虑 \mathbb{Z}/p\mathbb{Z} 上的多项式 f(x)=x^{p^n}-x。则 f'(x)=p^n x^{p^n-1}-1=-1，因此 f(x) 无重根。

令 E 为 f(x) 在 \mathbb{Z}/p\mathbb{Z} 上的分裂域，则 f(x) 在 E 中有 p^n 个不同的根。

设 S 为根的集合，则 \forall \alpha \in S，\alpha^{p^n}=\alpha，下面证明 S 是域。

因此 S 构成域。

因为 S 是 f(x) 的根集合，同时可证明 \mathbb{Z}/p\mathbb{Z}\subseteq S，因此 S 是 \mathbb{Z}/p\mathbb{Z} 的分裂域，即 S=E。

所以 E 是阶为 p^n 的域。

有限域上元素的表示

设 F_p=\mathbb{Z}/p\mathbb{Z}，q=p^n，只要找到 F_p 上一个 n 次不可约多 项式 f(x), 就有 F_q=F_p[x]/\langle f(x)\rangle。

其中加法和乘法都是模 f(x) 的多项式运算，乘法逆元可以通过扩展欧几里得算法求出。

代码实现时随机一个 n 次多项式，暴力判断是否可约即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(0x66ccff);
typedef vector<int> poly;
int m,P,n,inv[1005];
#define deg(f) (f.size()-1)
#define F(x) (poly{x})
inline poly operator +(poly a,poly b){
    if(deg(a)<deg(b))swap(a,b);
    for(int i=0;i<=deg(b);++i)a[i]=(a[i]+b[i])%P;
    while(deg(a)&&!a.back())a.pop_back();
    return a;
}
inline poly operator -(poly a,poly b){
    for(int i=0;i<=deg(b);++i)if(b[i])b[i]=P-b[i];
    return a+b;
}
inline poly operator *(poly a,poly b){
    poly c(deg(a)+deg(b)+1,0);
    for(int i=0;i<=deg(a);++i)for(int j=0;j<=deg(b);++j)
        c[i+j]=(c[i+j]+a[i]*b[j])%P;
    while(deg(c)&&!c.back())c.pop_back();
    return c;
}
inline pair<poly,poly> operator /(poly a,poly b){
    if(deg(a)<deg(b))return {F(0),a};
    if(!deg(a))return {F(a[0]*inv[b[0]]%P),F(0)};
    int o=1ll*a.back()*inv[b.back()]%P;
    poly c(deg(a)-deg(b)+1,0);
    c.back()=o;
    a=a-c*b;
    tie(a,b)=a/b;
    return {a+c,b};
}
poly exgcd(poly a,poly b,poly &X,poly &Y){
    auto [c,d]=a/b;
    if(d==F(0)){
        X=F(0),Y=F(inv[b.back()]);
        b=b*F(inv[b.back()]);
        return b;
    }
    poly g=exgcd(b,d,Y,X);
    Y=Y-c*X;
    return g;
}
bool check(){
    int x=m;
    if(x==1)return false;
    P=2;
    while(x%P!=0)++P;
    while(x%P==0)x/=P,++n;
    return x==1;
}
int ptoi(poly a){
    int b=0;
    for(int i=deg(a);~i;--i)b=b*P+a[i];
    return b;
}
poly itop(int b){
    if(!b)return F(0);
    poly a;
    while(b)a.push_back(b%P),b/=P;
    return a;
}
bool find(){
    poly f(n+1),X,Y,g;
    f[n]=1;
    for(int i=0;i<n;++i)f[i]=rnd()%P;
    for(int i=1;i<m;++i){
        g=exgcd(f,itop(i),X,Y);
        if(g!=F(1))return false;
    }
    for(int i=0;i<m;++i)for(int j=0;j<m;++j){
        X=itop(i),Y=itop(j);
        g=X+Y;
        tie(X,Y)=g/f;
        printf("%d%c",ptoi(Y)," \n"[j==m-1]);
    }
    for(int i=0;i<m;++i)for(int j=0;j<m;++j){
        X=itop(i),Y=itop(j);
        g=X*Y;
        tie(X,Y)=g/f;
        printf("%d%c",ptoi(Y)," \n"[j==m-1]);
    }
    return true;
}
int main(){
    scanf("%d",&m);
    if(!check())return puts("-1"),0;
    puts("0");
    inv[1]=1;
    for(int i=2;i<P;++i)inv[i]=(P-P/i)*inv[P%i]%P;
    while(!find());
    return 0;
}