本源多项式生成（原创java，可直接引用，由于二维码里面要运用又不想查表，于是自己手动写了个类，自动生成）
1、首先了解本源多项式定义：
二、 * 比如我们要求Gf(2)上的m次扩展的本原元n=2^m-1
* 那么它的充要条件是此多项式（f(x)）最高项为m次，f(x)为不可约多项式,f(x)能被x^n+1 整除 (f(x|x^n+1))
* 那么f(x)不能被x^q+1整除 1<=q<n
*
* 得出结论：1。f(x)的最高次项必为m次并且系数为1
* 2.f(x)为不可约多项式必不被x整除 也就是最后一项必须有一个1
* 3.如果m=1,f(x)=x+1
* 4:如果m>1,例如:m=4 这里的系数{0,1} 记 f(x)=x^4+a*x^3+b*x^2+c*x+1 那么它不能被x+1整除
* 那么当x=1时 f(1)=1+a+b+c+1=a+b+c!=0 也就是说a+b+c 中间为1的个数比为奇数
* 即比m次小并且不包括0次的系数和比为奇数 （减少迭代次数）
* 例如:f(x)=1+x+x^2+x^3+x^4 f1(x)=1+x+x^4
* 它们是否为本源多项式：第一项满足 中间和均为奇数
* 第二项 是否能被x^q+1整除 1<=q<n (n=2^4-1=15)
* 经过反复计算 f1(x)能被x^5+1 整除 f(x)不能被整除
三、由于研究时间太少，涉及的算法较简单，因此高阶运算较慢，慎用，最好是8阶以下，9阶有点慢了。测试了以下
这是一个九阶的生成示例图：
package com;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
/**
* Created by 常发均 on 2020/6/5.
* 本源多项式生成工具类
*/
public class bydxsUtil {
public String XYCODE;
public int ZCNUM;
public List<String> listBydxs=new ArrayList<String>();
public int KZNUM;//在几次的扩展number 就是m
public bydxsUtil(){}
public bydxsUtil(int KZNUM){
this.KZNUM=KZNUM;
dxssc();
}
public void dxssc(){
if(KZNUM<2){
return;
}
else if(KZNUM==2){
listBydxs.add("10");
return;
}else if(KZNUM==3){
listBydxs.add("110");
return;
}
/*
* 最外层循环表示个数 也就是中间个数为 奇数
* 然后层层递归 直至找到对应多项式
* 此算法实现原理：1、首先确定 第一项与最后一项 x^m+1
* 2、假定中间只有一个x项 如:x^m+x+1 ，x^m+x^2+1 ，x^m+x^3+1... (并指数从小到大，防止重复 )并将这些多项式存入集合中，
中间有两项：就是上一次的基础上在选择其他与自己不相同的项，当然选择的时候只能选择指数比自己大的项，防止重复 如：x^m+x+1 在它的基础上选择有x^m+x+x^2+1,x^m+x+x^3+1,x^m+x+x^4+1..x^m+x+x^(m-1)+1
中间有n项:在中间有n-1项的基础上进行选择 例如：x^m+x+..+x^(n-1)+1 选择有
x^m+x+..+x^(n-1)+x^n+1, x^m+x+..+x^(n-1)+x^(n+1)+1,‘’‘, x^m+x+..+x^(n-1)+x^(m-1)+1,
*
* */
LinkedHashMap<Integer,ArrayList<ArrayList<Integer>>> lmp=new LinkedHashMap<Integer, ArrayList<ArrayList<Integer>>>();
String code="";
for(int num=1;num<KZNUM;num++){
ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
if(num==1){
for(int i=1;i<KZNUM;i++){
ArrayList<Integer> list2=new ArrayList<Integer>();
list2.add(i);
list.add(list2);
}
}else{
ArrayList<ArrayList<Integer>> list2=lmp.get(num-1);
for(int i=0;i<list2.size();i++){
int a=list2.get(i).get(list2.get(i).size()-1);
if(a<KZNUM-1){
for(int j=a+1;j<KZNUM;j++){
ArrayList<Integer> list3=new ArrayList<Integer>();
for(int m=0;m<list2.get(i).size();m++){
list3.add(list2.get(i).get(m));
}
list3.add(j);
list.add(list3);
}
}
}
}
lmp.put(num,list);
}
for(Integer key:lmp.keySet()){
if(key%2==1){
for(int i=0;i<lmp.get(key).size();i++){
String str="";
for(int j=0;j<=KZNUM;j++){
if(j==0||j==KZNUM){
str+="1";
}else{
if(lmp.get(key).get(i).contains(j)){
str+="1";
}else{
str+="0";
}
}
}
if(bydxsxy(str)){
listBydxs.add(str);
}
}
}
}
}
/*
* 本源多项式效验
* */
public boolean bydxsxy(String code){
boolean flag=false;
if(code.length()<2){
return flag;
}
if(!code.substring(0,1).equals("1")||!code.substring(code.length()-1,code.length()).equals("1")){
return flag;
}
if(code.length()==2){
return true;
}
String str=code.substring(1,code.length()-1).replaceAll("0","");
if(str.length()%2==0){
return flag;
}
if(code.length()==3){
return true;
}
int n=(int)Math.pow(2,code.length()-1)-1;
/*
* 判断是否能被x^n+1整除 n=2^m-1
* ys="" 表示整除 否则不整除
* */
String ys=dxscf(getXn1(n),code);
if(ys.equals("")){
for(int i=2;i<n;i++){
if(i==code.length()-1){
continue;
}
String xyys=i>code.length()-1?dxscf(getXn1(i),code):dxscf(code,getXn1(i));
if(xyys.equals("")){
ZCNUM=i;
return flag;
}
}
}
else{
return flag;
}
return true;
}
/*
* 左移 使其最高此相同
* */
public String zy(String ys,String code){
String str=code;
if(ys.length()>code.length()){
for(int i=0;i<ys.length()-code.length();i++){
str=str+"0";
}
}
return str;
}
/*
* 获取x^n+1 的String 字符串
* */
public String getXn1(int n){
String str="";
for(int i=0;i<=n;i++){
if(i==0||i==n){
str+="1";
continue;
}
str+="0";
}
return str;
}
/*
* 除法的除数以及被除数
* */
public String dxscf(String str,String code){
String ys=str;
String cs="";
while(true){
if(ys.indexOf("1")==-1){
ys="";
}else{
ys=ys.substring(ys.indexOf("1"));
}
cs=zy(ys,code);
String zjzh="";
if(ys.length()==cs.length()){
for(int i=1;i<ys.length();i++){
int a=Integer.valueOf(ys.substring(i,i+1))+Integer.valueOf(cs.substring(i,i+1));
a=a%2;
zjzh+=a+"";
}
ys=zjzh;
}else{
break;
}
}
return ys;
}
public static void main(String[] args) {
bydxsUtil by=new bydxsUtil(9);
System.out.println("=="+by.listBydxs.size());
for(int i=0;i<by.listBydxs.size();i++){
String str="";
for(int j=0;j<by.listBydxs.get(i).length()-1;j++){
if(by.listBydxs.get(i).substring(j,j+1).equals("1")){
str+="x^"+(by.listBydxs.get(i).length()-j-1)+"+";
}
}
str+="1";
System.out.println(str);
}
}
}