有关多项式的算法——四则运算、求逆
算法介绍 多项式的运算可以说比之前的多精度数运算还要简单一点，因为多项式的加减只能存在于同次数的项之间，所以不需要考虑加减法里面的进位退位问题，这也就使得乘除法简单了很多。 加减法的原理就没什么好说的了，乘除法都是基于多精度数的算法修改的，存储多项式也使用了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))$ ，所以可通过查表也很容易求出元素的逆元。...