以下贴代码，可以用来验证关于 \(\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;
}
}