---

---

前言

本篇文章介绍的是uestc信息安全与数学基础实验四,有限域上运算的实现，仅作参考。

---

一、实验原理

取域 $F_2$ 上的8次不可约多项式是$f(x)=x^8+x^6+x^5+x+1,\alpha$ 是 $f(x)$的一个根。因此有限域$F_{2^8}$可以表示为$\alpha$的所有$F_2$ 次数小于8的多项式集合，即

F 2 8 = a 7 α 7 + a 6 α 6 + a 5 α 5 + a 4 α 4 + a 3 α 3 + a 2 α 2 + a 1 α + a 0 ∣ a i ∈ { 0 , 1 } F_{2^8}={a_7\alpha^7+a_6\alpha^6+a_5\alpha^5+a_4\alpha^4+a_3\alpha^3+a_2\alpha^2+a_1\alpha+a_0|a_i\in{\{0,1\}}} F28​=a7​α7+a6​α6+a5​α5+a4​α4+a3​α3+a2​α2+a1​α+a0​∣ai​∈{0,1}

定义一个由$a_7{a}_6{a}_5{a}_4{a}_3{a}_2{a}_1{a}_0$组成的字节$a$可表示为系数为$0，1$的二进制多项式：

$$a_7{\alpha }^7+a_6{\alpha }^6+a_5{\alpha }^5+a_4{\alpha }^4+a_3{\alpha }^3+a_2{\alpha }^2+a_1\alpha +a_0$$

还可以将每个字节表示为一个16进制数，即每4比特表示一个16进制数，代表较高位的4比特的符号仍在左边。例如，01101011可表示为6B。同样也可以用0-255这256个十进制整数来表示域$F_{2^8}$中的元素。它们之间的运算为$F_{2^8}$中的运算，其加法定义为二进制多项式的加法，且其系数模2，其乘法定义为多项式的乘积模一个次数为8的不可约多项式$f(\alpha )$。通过计算机实验可以验证元素“02”是域$F_{2^8}$中的一个本原元。

将域$F_{2^8}$中的元素用0-255这256个十进制整数来表示，指数对数表可以通过如下步骤来构建：

（1）将元素‘02’表示成为$\alpha$，依次计算，${\alpha }^i\mathrm{mod}(f(\alpha )),i=0,1,...,254$，将所得结果转变为十进制数，设为${\beta }_i,i=0,1,...,254$；如下表所示：

（2）建表。第一行为$0,1,...,254,255$第二行元素依次为${\beta }_i,i=0,1,...,254$。由于${\alpha }^0\equiv {\alpha }^{255}\mathrm{mod}(f(\alpha ))$，约定第2行，第255列元素为0。

0	1	2	3	…	253	254	255
1	2	4	8	…	233	177	0

（3）按所建表的第二行元素的大小进行重排列，如下表所示：

255	0	1	197	…	72	230	104
0	1	2	3	…	253	254	255

（4）将（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,…,254,均有$({\alpha }^i{)}^{-1}\equiv {\alpha }^{255-i}\mathrm{mod}(f(\alpha ))$，所以可通过查表也很容易求出元素的逆元。

二、解释

简单来说就是建一个表，然后在进行该域上多项式的计算时借助查表可以更快的算出逆元等值。
例如：

三、代码实现

我创建了负责函数运行的GF类，负责建表的Table类，以及Table类的子类—负责进行多项式计算的GFOpera类，还引用了实验三里的方法。
依次如下：

GF类

package Experiment.Experiment4;  
  
import java.util.Scanner;  
  
public class GF {  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        System.out.println("输入两个多项式:");  
        System.out.print("F = ");  
        String str1 = sc.nextLine();  
        System.out.print("G = ");  
        String str2 = sc.nextLine();  
        int[] F = new int[str1.length()];  
        for (int i = 0; i < str1.length(); i++) {  
            F[i] = str1.charAt(i) - '0';  
        }  
        int[] G = new int[str2.length()];  
        for (int i = 0; i < str2.length(); i++) {  
            G[i] = str2.charAt(i) - '0';  
        }  
        GFOpera gfOpera = new GFOpera(F,G);  
        System.out.print("乘积:");  
        Print(gfOpera.Mul());  
        System.out.print("F逆元:");  
        Print(gfOpera.InverseElF());  
        System.out.print("G逆元:");  
        Print(gfOpera.InverseElG());  
    }  
    public static void Print(int[] x) {         //打印数组结果，次项由低到高  
        for (int i = 0; i < x.length; i++) {  
            System.out.print(x[i]);  
        }  
        System.out.println();  
    }  
}

Table类

package Experiment.Experiment4;  
import Experiment.Experiment3.*;  
//获得指数对数表  
public class Table {  
    public int Pri = 2;                             //本原元  
    public int[] Fx = new int[]{1,1,0,0,0,1,1,0,1}; //不可约多项式  
    public int M = (int) Math.pow(2,8);             //用来取模的书  
    public int[] Table;                             //指数对数表  
  
    //构造函数  
    public Table() {  
        Table = new int[M];  
        Table[0] = M - 1;  
        for (int i = 0; i < M-  1; i++) {           //在循环中创建指数对数表  
            int[] Gx = new int[i + 1];              //利用本原元生成多项式  
            Gx[i] = 1;  
            ResultMod resultMod = new Multinomial(2,Gx,Fx).Mod();//模不可约多项式得到余多项式  
            int m = BinaryToDecimal(resultMod.getR());//将余多项式带入本原元转化为对应值存到表里  
            Table[m] = i;  
        }  
    }  
    //二进制转十进制算法  
    public int BinaryToDecimal(int[] Fx) {  
        int sum = 0;  
        for (int i = 0; i < Fx.length; i++) {  
            sum += Fx[i] * (int)Math.pow(Pri, i);  
        }  
        return sum;  
    }  
}

GFOpera类

package Experiment.Experiment4;  
import Experiment.Experiment3.*;  
  
//进行域内的操作  
public class GFOpera extends Table {                            //作为该域指数对数表的子类，便于调用本原元之类的变量  
    private int logF;                                           //两个多项式对应的对数值  
    private int logG;  
  
    //构造函数  
    public GFOpera(int[] F,int[] G) {  
        this.logF = Table[BinaryToDecimal(F)];                  //获得对数值  
        this.logG = Table[BinaryToDecimal(G)];  
    }  
  
    //多项式乘法 f * g    public int[] Mul() {  
        int index =  (logG + logF) % (M - 1);                   //根据本原元取模的得到目标多项式Gx的序号  
        int[] Gx = new int[index + 1];                          //得到目标多项式  
        Gx[index] = 1;  
        ResultMod resultMod = new Multinomial(2,Gx,Fx).Mod();//调用实验三的多项式取模，进行模不可约多项式，得到结果  
        return resultMod.getR();  
    }  
  
    //求F的逆元  
    public int[] InverseElF() {  
        int index = M - 1 - logF;                               //得到目标多项式的序号，以下操作同上  
        int[] Gx = new int[index + 1];  
        Gx[index] = 1;  
        ResultMod resultMod = new Multinomial(2,Gx,Fx).Mod();  
        return resultMod.getR();  
    }  
    //求G的逆元  
    public int[] InverseElG() {  
        int index = M - 1 - logG;  
        int[] Gx = new int[index + 1];  
        Gx[index] = 1;  
        ResultMod resultMod = new Multinomial(2,Gx,Fx).Mod();  
        return resultMod.getR();  
    }  
}

运行示例

即满足：
$(1+x+x^2+x^3+x^4+x^5+x^6)(1+x^2+x^4+x^5)=1+x^2+x^3+x^6$
$(1+x+x^2+x^3+x^4+x^5+x^6)(x^3+x^7)=1$
$(1+x^2+x^4+x^5)(x+x^5+x^7)=1$

---

总结

该实验的关键部分是建表，具体思路还是比较简单的，实现起来也比较简单（但是实验三的方法要正确实现，该实验才能不出问题）。可能有些地方可以实现地更好，编者不才只能做到这种程度了，请见谅。