（可直接食用）在有限素域上的因式分解代码

以下贴代码，可以用来验证关于 \(\mathbb{F}_p [x]\) 上的多项式的不可约性 / 或寻找真因式。时间复杂度非常高。

• 寻找 \(\mathbb{F}_p [x]\) 上的 \(k\) 阶不可约多项式，以构造 \(p^k\) 域.

• 验证 \(\mathbb{F}_2 [x]\) 上的多项式 \(x^{2^k}+x+1\) 是可约的，如果 \(k\ge 3\).

#include<bits/stdc++.h>
using namespace std;

using poly=vector<int>;
const int P=2; // it must be some prime number 
poly f(1000);

void fix(poly&a)
{while(!a.empty()&&!a.back())a.pop_back();}

void print(const poly&a){
	putchar('(');
	int fst=0;
	for(int i=0;i<(int)a.size();++i)
		if(a[i]){
			if(fst)putchar('+');
			fst=1;
			if(i==0)printf("%d",a[i]);
			else {
				if(a[i]!=1)printf("%d",a[i]);
				putchar('x');
				if(i>1)printf("^%d",i);
			}
		}
	putchar(')');
}

pair<poly,poly> div(poly a,const poly&b){
	int m=a.size(),n=b.size();
	poly q(m);
	for(int i=m-1;i>=n-1;--i)
		if(a[i]){
			q[i-(n-1)]=a[i];
			int t=P-a[i];
			for(int j=0;j<n;++j)
				a[i-j]=(a[i-j]+t*b[j])%P;
		}
	fix(a);fix(q);
	return {q,a};
}

int ok;
poly temp;

void dfs(int d)
{
	if(ok)
		return;
	if(d<0)
	{
		auto res=div(f,temp);
		if(res.second.empty()) // temp|f
			ok=1;
		return;
	}
	for(int j=0;j<P&&!ok;++j)
	{
		temp[d]=j;
		dfs(d-1);
	}
}

int main(){
	f[0]=f[1]=1;f[64]=1; // input the polynomial as f[i] = a_i (x^i)
	fix(f);
	print(f);putchar('=');
	while(1){
		ok=0;
		for(int k=1;2*k<(int)f.size()&&!ok;++k)
		{
			temp=poly(k+1);temp[k]=1;
			dfs(k-1);
		}
		if(!ok)
		{
			print(f);
			break;
		}
		print(temp);
		f=div(f,temp).first;
	}
}