算法介绍
多项式的运算可以说比之前的多精度数运算还要简单一点，因为多项式的加减只能存在于同次数的项之间，所以不需要考虑加减法里面的进位退位问题，这也就使得乘除法简单了很多。
加减法的原理就没什么好说的了，乘除法都是基于多精度数的算法修改的，存储多项式也使用了ArrayList，索引值对应项的次数，其元素大小对应项的系数。
求逆则使用了欧几里得算法：
以及有限域 $F_{2^8}$ 上基于指数对数表的乘法和求逆，对应的不可约多项式 $f(x)=x^8+x^6+x^5+x+1$ 。
指数对数表的构建方法如下：
- 将元素$02$表示成为$\alpha$，依次计算 $\alpha^i\space modf(\alpha)\space,i=0,1,\cdots, 254$ ,将所得结果转变为十进制数，设为$\beta_i ,i=0,1,\cdots, 254$；
- 建表。第一行为 $\alpha_i ,i=0,1,\cdots, 254$，第二行元素依次为 $\beta_i ,i=0,1,\cdots, 254$。由于 $\alpha^0\equiv\alpha^{255}\space modf(\alpha)$，约定第$2$行，第$255$列元素为$0$；
| 0 | 1 | 2 | 3 | … | 253 | 254 | 255 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 4 | 8 | … | 233 | 177 | 0 |
- 按所建表的第二行元素的大小进行重排列；
| 255 | 0 | 1 | 197 | … | 72 | 230 | 104 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | … | 253 | 254 | 255 |
- 将（3）中表的第一行放在（2）中表的第三行。
| 序号 | 0 | 1 | 2 | 3 | … | 253 | 254 | 255 |
|---|---|---|---|---|---|---|---|---|
| $(02)^i$ | 1 | 2 | 4 | 8 | … | 233 | 177 | 0 |
| $log_{(02)^i}$ | 255 | 0 | 1 | 197 | … | 72 | 230 | 104 |
建立上述指数对数表之后，通过查表很容易求出两个元素的乘积。又由于对于 $i=0,1,\cdots, 254$ 均有 $(\alpha^i)^{-1}\equiv\alpha^{255-i}mod(f(\alpha))$ ，所以可通过查表也很容易求出元素的逆元。
下面是完整代码：
有理数域的多项式计算算法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/***************************************
* Created By HuJiekang on 2019/12/12. *
***************************************/
public class Polynomial {
/**
* 此方法用于快速创建一个ArrayList对象
* @param elements 为整个整数的每一位数字
* @return ArrayList<Double>
*/
public static ArrayList<Double> CreateArrayList(double ... elements) {
ArrayList<Double> list = new ArrayList<>();
for (Double element : elements) {
list.add(element);
}
return list;
}
/**
* 此方法用于比较两个数的大小。若第一个数大于等于第二个数则返回true，否则返回false
* @params num1, num2 为要比较的数
* @return 返回比较结果 boolean
*/
public static boolean isBigger(ArrayList<Double> num1, ArrayList<Double> num2) {
if(num1.size() < num2.size()) return false;
else if(num1.size() > num2.size()) return true;
else {
for (int i = num1.size()-1; i >=0; i--){
if(num1.get(i)<num2.get(i)) return false;
else if(num1.get(i)>num2.get(i)) return true;
}
}
return true;
}
/**
* 此方法用于将一个多项式格式化输出为∑aix^i的形式
* @param d 要输出的多项式
* @return void
*/
public static void DisplayPolynomial(ArrayList<Double> d){
for(int i = 0;i<d.size();i++){
if(d.get(i)==0.0) continue;
if(i==0) System.out.print(d.get(i));
else if(i==1) System.out.print(d.get(i)+" * x");
else{
System.out.print(d.get(i)+" * x^"+i);
}
if(i==d.size()-1) break;
else System.out.print(" + ");
}
}
/**
* 此方法实现了多项式的加法计算
* @params pol1,pol2 要进行运算的两个多项式
* @return ArrayList<Double>
*/
public static ArrayList<Double> PolynomialPlus(ArrayList<Double> pol1, ArrayList<Double> pol2){
ArrayList<Double> result = new ArrayList<>();
int i;
for(i = 0;i<Math.min(pol1.size(), pol2.size());i++){
result.add(i, pol1.get(i)+pol2.get(i));
}
for(;i<Math.max(pol1.size(), pol2.size());i++){
result.add(i, pol1.size()>=pol2.size()?pol1.get(i):pol2.get(i));
}
while(result.get(result.size()-1)==0) {
result.remove(result.size() - 1);
}
return result;
}
/**
* 此方法实现了多项式的减法计算
* @params pol1,pol2 要进行运算的两个多项式
* @return ArrayList<Double>
*/
public static ArrayList<Double> PolynomialSub(ArrayList<Double> pol1, ArrayList<Double> pol2){
ArrayList<Double> result = new ArrayList<>();
int i;
for(i = 0;i<Math.min(pol1.size(), pol2.size());i++){
result.add(i, pol1.get(i)-pol2.get(i));
}
for(;i<Math.max(pol1.size(), pol2.size());i++){
result.add(i, pol1.size()>=pol2.size()?pol1.get(i):pol2.get(i)*-1);
}
while(result.get(result.size()-1)==0) {
result.remove(result.size() - 1);
}
return result;
}
/**
* 此方法实现了多项式的乘法计算
* @params pol1,pol2 要进行运算的两个多项式
* @return ArrayList<Double>
*/
public static ArrayList<Double> PolynomialMult(ArrayList<Double> pol1, ArrayList<Double> pol2){
ArrayList<Double> result = new ArrayList<>();
for(int i = 0;i<=pol1.size()-1+pol2.size()-1;i++){
result.add(0.0);
}
for(int i = 0;i<pol1.size();i++){
for(int j = 0;j<pol2.size();j++){
result.set(i+j, result.get(i+j)+pol1.get(i)*pol2.get(j));
}
}
return result;
}
/**
* 此方法实现了多项式的带余除法计算
* @params pol1,pol2 要进行运算的两个多项式
* @return 包含结果的List
*/
public static List<ArrayList<Double>> PolynomialDiv(ArrayList<Double> pol1, ArrayList<Double> pol2){
if(pol2==null||(pol2.size()==1&&pol2.get(0)==0.0)) throw new ArithmeticException("/ by zero");
if(pol1 == pol2) return Arrays.asList(CreateArrayList(1.0),CreateArrayList(0.0));
if(pol1==null||(pol1.size()==1&&pol1.get(0)==0.0)) return Arrays.asList(CreateArrayList(0.0), CreateArrayList(0.0));
if(!isBigger(pol1, pol2)) return Arrays.asList(CreateArrayList(0.0), pol1);
ArrayList<Double> result = new ArrayList<>();
for (int i=0;i<pol1.size();i++){
result.add(i,0.0);
}
ArrayList<Double> pol2_duiqi = (ArrayList<Double>) pol2.clone();
int mult_times = 0;
double times;
while(pol2_duiqi.size()!=pol1.size()){
pol2_duiqi.add(0, 0.0 );
mult_times++;
}
while(true) {
if(pol1.size()==0) break;
if(pol1.size()==pol2_duiqi.size()){
times = pol1.get(pol1.size()-1)/pol2_duiqi.get(pol1.size()-1);
for(int i = 0;i<pol1.size();i++){
pol1.set(i, pol1.get(i)-pol2_duiqi.get(i)*times);
}
pol1.set(pol1.size()-1, 0.0);
}else{
times = 0.0;
}
if(pol1.size()!=0){
while(pol1.get(pol1.size()-1)==0){
pol1.remove(pol1.size()-1);
if(pol1.isEmpty()){
break;
}
}
}
result.set(mult_times, times);
if (pol2_duiqi.get(0) == 0 && pol2_duiqi.size() > pol2.size()){
pol2_duiqi.remove(0);
mult_times--;
}
else{
break;
}
}
while(result.get(result.size()-1)==0){
result.remove(result.size()-1);
}
if(pol1.size()==0){
return Arrays.asList(result,CreateArrayList(0));
}
return Arrays.asList(result,pol1);
}
/**
* 此方法实现了扩展的欧几里得算法，用于计算多项式的逆元
* @params pol1,pol2 要进行运算的两个多项式
* @return 包含结果的List
*/
public static List<ArrayList<Double>> Euclid(ArrayList<Double> pol1, ArrayList<Double> pol2){
if(pol2==null||(pol2.size()==1&&pol2.get(0)==0.0)) return Arrays.asList(pol1, CreateArrayList(1.0), CreateArrayList(0.0));
ArrayList<Double> u1x = CreateArrayList(0.0);
ArrayList<Double> u2x = CreateArrayList(1.0);
ArrayList<Double> v1x = CreateArrayList(1.0);
ArrayList<Double> v2x = CreateArrayList(0.0);
ArrayList<Double> qx;
ArrayList<Double> rx;
ArrayList<Double> ux;
ArrayList<Double> vx;
List tmp;
while(!(pol2.size() == 1 && pol2.get(0) == 0.0)){
tmp = PolynomialDiv(pol1, pol2);
qx = (ArrayList<Double>) tmp.get(0);
rx = (ArrayList<Double>) tmp.get(1);
ux = PolynomialSub(u2x, PolynomialMult(qx, u1x));
vx = PolynomialSub(v2x, PolynomialMult(qx, v1x));
pol1 = pol2;
pol2 = rx;
u2x = u1x;
u1x = ux;
v2x = v1x;
v1x = vx;
}
return Arrays.asList(pol1, u2x, v2x);
}
}
GF(256)域的多项式计算算法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/***************************************
* Created By HuJiekang on 2019/12/15. *
***************************************/
public class Galois_256 {
//2^8域上的8次不可约多项式
public static final int IRREDUCIBLE_POLYNOMIAL = 355;
public static void main(String[] args) {
ArrayList<Integer> d1 = CreateArrayList(2);
ArrayList<Integer> d2 = CreateArrayList(139);
for (int i = 1; i < 256; i++) {
System.out.print(i + "^-1=" + ArrayListToInt(GaloisInverseWithSheet(CreateArrayList(i))));
System.out.println("\t"+i + "^-1=" + ArrayListToInt(GaloisEuclid(CreateArrayList(i))));
}
}
/**
* 此方法用于快速创建一个ArrayList对象
*
* @param element 为一个数字
* @return ArrayList<Integer>
*/
public static ArrayList<Integer> CreateArrayList(int element) {
ArrayList<Integer> list = new ArrayList<>();
String[] s = Integer.toBinaryString(element).split("");
for (String ss : s) {
list.add(Integer.parseInt(ss));
}
while (list.size() < 8) list.add(0, 0);
return list;
}
/**
* 此方法用于比较两个数的大小。若第一个数大于等于第二个数则返回true，否则返回false
* 参数 num1, num2 为要比较的数
* 返回比较结果 boolean
*/
public static boolean isBigger(ArrayList<Integer> num1, ArrayList<Integer> num2) {
if (num1.size() < num2.size()) return false;
else if (num1.size() > num2.size()) return true;
return true;
}
/**
* 此方法用于将多项式对象转化为2^8域上对应的序号
*
* @param element 要进行转换的多项式
* @return int
*/
public static int ArrayListToInt(ArrayList<Integer> element) {
String s = "";
for (int i : element) {
s += String.valueOf(i);
}
return Integer.parseInt(s, 2);
}
/**
* 此方法实现了2^8有限域上的多项式加法
*
* @return ArrayList<Integer>
* @params pol1, pol2
*/
public static ArrayList<Integer> GaloisPlus(ArrayList<Integer> pol1, ArrayList<Integer> pol2) {
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < 8; i++) {
result.add(i, pol1.get(i) ^ pol2.get(i));
}
return result;
}
/**
* 此方法实现了2^8有限域上的多项式减法
*
* @return ArrayList<Integer>
* @params pol1, pol2
*/
public static ArrayList<Integer> GaloisSub(ArrayList<Integer> pol1, ArrayList<Integer> pol2) {
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < 8; i++) {
result.add(i, pol1.get(i) ^ pol2.get(i));
}
return result;
}
/**
* 此方法实现了2^8有限域上的多项式乘法
*
* @return ArrayList<Integer>
* @params pol1, pol2
*/
public static ArrayList<Integer> GaloisMult(ArrayList<Integer> pol1, ArrayList<Integer> pol2) {
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i <= pol1.size() - 1 + pol2.size() - 1; i++) {
result.add(0);
}
for (int i = 0; i < pol1.size(); i++) {
for (int j = 0; j < pol2.size(); j++) {
result.set(i + j, result.get(i + j) ^ (pol1.get(i) & pol2.get(j)));
}
}
while (result.size() > 8 && result.get(0) == 0) result.remove(0);
return GaloisDiv(result, CreateArrayList(IRREDUCIBLE_POLYNOMIAL)).get(1);
}
/**
* 此方法实现了2^8有限域上的多项式带余除法
*
* @param pol1 被除式
* @param pol2 除式
* @return 余式
*/
public static List<ArrayList<Integer>> GaloisDiv(ArrayList<Integer> pol1, ArrayList<Integer> pol2) {
boolean isZero1 = true;
boolean isZero2 = true;
for (int i : pol1) {
if (i != 0) {
isZero1 = false;
break;
}
}
for (int i : pol2) {
if (i != 0) {
isZero2 = false;
break;
}
}
if (pol2 == null || isZero2) throw new ArithmeticException("/ by zero");
if (pol1 == pol2) return Arrays.asList(CreateArrayList(1), CreateArrayList(0));
if (pol1 == null || isZero1) return Arrays.asList(CreateArrayList(0), CreateArrayList(0));
ArrayList<Integer> pol2_duiqi = (ArrayList<Integer>) pol2.clone();
while (pol2_duiqi.get(0) == 0) pol2_duiqi.remove(0);
while (pol1.get(0) == 0) pol1.remove(0);
if (!isBigger(pol1, pol2_duiqi)) {
while (pol1.size() < 8) pol1.add(0, 0);
return Arrays.asList(CreateArrayList(0), pol1);
}
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < pol1.size(); i++) {
result.add(i, 0);
}
int orgSize = pol2_duiqi.size();
int multTimes = 0;
int times = 0;
while (pol2_duiqi.size() != pol1.size()) {
pol2_duiqi.add(pol2_duiqi.size(), 0);
multTimes++;
}
while (true) {
if (pol1.size() == pol2_duiqi.size()) {
for (int i = 0; i < pol1.size(); i++) {
pol1.set(i, pol1.get(i) ^ pol2_duiqi.get(i));
}
times = 1;
}
if (pol1.size() != 0) {
while (pol1.get(0) == 0) {
pol1.remove(0);
if (pol1.size() < orgSize) {
break;
}
}
}
result.set(multTimes, times);
if (pol2_duiqi.get(pol2_duiqi.size() - 1) == 0 && pol2_duiqi.size() > orgSize) {
pol2_duiqi.remove(pol2_duiqi.size() - 1);
multTimes--;
} else {
break;
}
times = 0;
}
Collections.reverse(result);
while (result.size() > 8 && result.get(0) == 0) result.remove(0);
while (pol1.size() < 8) pol1.add(0, 0);
while (result.size() < 8) result.add(0, 0);
return Arrays.asList(result, pol1);
}
/**
* 此方法实现了2^8有限域上的多项式扩展欧几里得算法
*
* @param fx 要进行计算的多项式
* @return 多项式逆元
*/
public static ArrayList<Integer> GaloisEuclid(ArrayList<Integer> fx) {
ArrayList<Integer> gx = CreateArrayList(IRREDUCIBLE_POLYNOMIAL);
ArrayList<Integer> u1x = CreateArrayList(0);
ArrayList<Integer> u2x = CreateArrayList(1);
ArrayList<Integer> v1x = CreateArrayList(1);
ArrayList<Integer> v2x = CreateArrayList(0);
ArrayList<Integer> qx;
ArrayList<Integer> rx;
ArrayList<Integer> ux;
ArrayList<Integer> vx;
List tmp;
boolean isOne = true;
for (int i = 0; i < fx.size(); i++) {
if (fx.get(i) != v1x.get(i)) isOne = false;
}
if (isOne) return CreateArrayList(0);
while (true) {
boolean isZero = true;
for (int i : gx) {
if (i != 0) isZero = false;
}
if (isZero) break;
tmp = GaloisDiv(fx, gx);
qx = (ArrayList<Integer>) tmp.get(0);
rx = (ArrayList<Integer>) tmp.get(1);
ux = GaloisSub(u2x, GaloisMult(qx, u1x));
vx = GaloisSub(v2x, GaloisMult(qx, v1x));
fx = gx;
gx = rx;
u2x = u1x;
u1x = ux;
v2x = v1x;
v1x = vx;
}
return u2x;
}
/**
* 此方法生成2^8域的指数对数表
*
* @return int[][]
*/
public static int[][] LogarithmSheet() {
int[][] sheet = new int[2][256];
ArrayList<Integer> baseElement = CreateArrayList(2);
ArrayList<Integer> element = CreateArrayList(1);
sheet[0][255] = 0;
for (int i = 0; i < 255; i++) {
sheet[0][i] = ArrayListToInt(element);
element = GaloisMult(element, baseElement);
}
for (int i = 0; i < 256; i++) {
sheet[1][sheet[0][i]] = i;
}
return sheet;
}
/**
* 此方法使用指数对数表计算2^8域上的多项式乘法
*
* @return ArrayList<Integer>
* @params pol1, pol2
*/
public static ArrayList<Integer> GaloisMultWithSheet(ArrayList<Integer> pol1, ArrayList<Integer> pol2) {
int[][] sheet = LogarithmSheet();
int num1 = ArrayListToInt(pol1);
int num2 = ArrayListToInt(pol2);
return CreateArrayList(sheet[0][(sheet[1][num1] + sheet[1][num2]) % 255]);
}
/**
* 此方法使用指数对数表计算2^8域上的多项式多项式逆元
*
* @param pol 要求逆元的多项式
* @return ArrayList<Integer>
*/
public static ArrayList<Integer> GaloisInverseWithSheet(ArrayList<Integer> pol) {
int[][] sheet = LogarithmSheet();
int num = ArrayListToInt(pol);
return CreateArrayList(sheet[0][255 - sheet[1][num]]);
}
}