专栏文章

有限域结构定理

CC1942huangjiaxu管理员
P3923题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipfng0l
此快照首次捕获于
2025/12/03 11:13
3 个月前
此快照最后确认于
2025/12/03 11:13
3 个月前
查看原文
结构定理一： 设 FF 是一个特征为素数 pp 的有限域，则 FF 中的元素个数为 pnp^n，nn 是一个正整数。
证明： 由于 FF 是一个特征为 pp 的有限域，所以 FF 的素子域与 Z/pZ\mathbb{Z}/p\mathbb{Z} 同构。因此 FF 是 Z/pZ\mathbb{Z}/p\mathbb{Z} 的有限扩张，设扩张次数为 nn，且 a1,a2,⋯，ana_1,a_2,\cdots ，a_n 是 FF 在 Z/pZ\mathbb{Z}/p\mathbb{Z} 上的一组基。则 F={b1a1+b2a2+⋯+bnan∣bi∈Z/pZ,i=1,2,⋯ ,n}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\}，所以 FF 中的元素个数为 pnp^n。
引理一： 如果 f(x)f(x) 在 FF 上不可约，则 F[x]/⟨f(x)⟩F[x]/\langle f(x)\rangle 是一个域。
证明： 模 f(x)f(x) 同余是 F[x]F[x] 上的一个等价关系。不难证明 F[x]/⟨f(x)⟩F[x]/\langle f(x)\rangle 是个含幺交换环。
只要证明任意非 00 元有乘法逆元，设 r(x)≠0∈F[x]/⟨f(x)⟩r(x)\neq 0\in F[x]/\langle f(x)\rangle，则 0≤deg⁡(r(x))<deg⁡(f(x))0\le \operatorname{deg}(r(x))\lt\operatorname{deg}(f(x))，因为 f(x)f(x) 在 FF 上不可约，所以 gcd⁡(f(x),r(x))=1\gcd(f(x),r(x))=1，因此 r(x)r(x) 在 F[x]/⟨f(x)⟩F[x]/\langle f(x)\rangle 中有乘法逆元。
引理二： 域 FF 上任意一个次数 ≥1\ge 1 的多项式 f(x)f(x) 在 FF 上都有分裂域。
证明： 对多项式次数 nn 进行数学归纳：
  • 若 n=1n=1，f(x)=a(x−α)f(x)=a(x-\alpha)，则 FF 本身即为分裂域。
  • 归纳假设：假设对任意域 KK 及次数 <n\lt n 的多项式 g(x)∈K[x]g(x)\in K[x]，均存在分裂域。
任取 f(x)f(x) 的一个不可约因子 p(x)p(x)，定义 F1=F[x]/⟨p(x)⟩F_1=F[x]/\langle p(x)\rangle，则 F1F_1 是个域，且令 α=x+⟨p(x)⟩∈F1\alpha=x+\langle p(x)\rangle \in F_1，p(α)=p(x)+⟨p(x)⟩=0+⟨p(x)⟩p(\alpha)=p(x)+\langle p(x)\rangle=0+\langle p(x)\rangle，所以 α\alpha 是 p(x)p(x) 的根。
在域 F1F_1 上，将 f(x)f(x) 写为 (x−α)⋅g(x)(x-\alpha)\cdot g(x)，g(x)∈F1g(x)\in F_1。
此时 deg⁡(g(x))=n−1\operatorname{deg}(g(x))=n-1，根据归纳假设，g(x)g(x) 在 F1F_1 上存在分裂域 EE。可以验证 EE 是 f(x)f(x) 在 FF 上的分裂域。
结构定理二（存在性）： 对于任何素数 pp 和任意正整数 nn， 总存在一个有限域恰好含有 pnp^n 个元素。
证明： 考虑 Z/pZ\mathbb{Z}/p\mathbb{Z} 上的多项式 f(x)=xpn−xf(x)=x^{p^n}-x。则 f′(x)=pnxpn−1−1=−1f'(x)=p^n x^{p^n-1}-1=-1，因此 f(x)f(x) 无重根。
令 EE 为 f(x)f(x) 在 Z/pZ\mathbb{Z}/p\mathbb{Z} 上的分裂域，则 f(x)f(x) 在 EE 中有 pnp^n 个不同的根。
设 SS 为根的集合，则 ∀α∈S\forall \alpha \in S，αpn=α\alpha^{p^n}=\alpha，下面证明 SS 是域。
  • 加法封闭：∀α,β∈S\forall \alpha,\beta \in S，(α+β)pn=αpn+βpn=α+β(\alpha+\beta)^{p^n}=\alpha^{p^n}+\beta^{p^n}=\alpha+\beta
  • 乘法封闭：∀α,β∈S\forall \alpha,\beta \in S，(αβ)pn=αpnβpn=αβ(\alpha\beta)^{p^n}=\alpha^{p^n}\beta^{p^n}=\alpha\beta。
  • 加法逆元：∀α∈S\forall \alpha \in S，若 p=2p=2 则 α=−α\alpha =-\alpha，否则 (−α)pn=(−1)pnαpn=−α(-\alpha)^{p^n}=(-1)^{p^n}\alpha^{p^n}=-\alpha
  • 乘法逆元：∀α∈S\forall \alpha \in S，(α−1)pn=(αpn)−1=α−1(\alpha^{-1})^{p^n}=(\alpha^{p^n})^{-1}=\alpha^{-1}
因此 SS 构成域。
因为 SS 是 f(x)f(x) 的根集合，同时可证明 Z/pZ⊆S\mathbb{Z}/p\mathbb{Z}\subseteq S，因此 SS 是 Z/pZ\mathbb{Z}/p\mathbb{Z} 的分裂域，即 S=ES=E。
所以 EE 是阶为 pnp^n 的域。
有限域上元素的表示
设 Fp=Z/pZF_p=\mathbb{Z}/p\mathbb{Z}，q=pnq=p^n，只要找到 FpF_p 上一个 nn 次不可约多 项式 f(x)f(x), 就有 Fq=Fp[x]/⟨f(x)⟩F_q=F_p[x]/\langle f(x)\rangle。
其中加法和乘法都是模 f(x)f(x) 的多项式运算，乘法逆元可以通过扩展欧几里得算法求出。
代码实现时随机一个 nn 次多项式，暴力判断是否可约即可。
参考代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...