有关多项式的算法——四则运算、求逆

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

Dec. 18, 2019 · 8 min · 1500 words

多精度数的四则运算-Java和Python实现

多精度数指的是位数超过1024Bit的数。由于这一类数的位数超过了计算机CPU寄存器表达,也就是超出了计算机的字长,所以不能够使用计算机进行直接的运算。除此之外,多精度数的大小也超出了计算机中定义的整型变量的最大大小,所以也不能使用标准的整型来存储这一类数,而需要使用数组或是字符串来存储。 对于多精度数的计算,目前有两种处理办法: 模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。 这个方法的优点是操作逻辑符合人们的日常思维,易于理解,缺点是效率较低。 将多精度数当作一个二进制流进行处理,使用各种移位和逻辑操作来进行加减乘除运算。 这个方法的优点是执行效率高,缺点是代码极其复杂,可读性低,难以理解。 下面的算法都是基于第一种办法进行处理。 算法原理 先重新理一下竖式计算的流程: 加法在手工竖式计算中,当两个位相加得到的值大于10时就会产生一个进位值,并会在高一位的计算中把进位值也加入计算,这样从低位到高位一直计算直到计算结束为止。所以在算法中也需要定义一个进位值的变量。 减法与加法类似,当被减数位小于减数位时,会产生一个退位值,即向更高一位去借10,来避免产生负数。若这一位产生了借位,那么高一位的计算中就要减去1再进行计算。所以在算法中也需要定义一个退位值的变量。 乘法的运算在竖式计算中是把乘数逐位的与被乘数相乘,且运算结果随着乘数的位数向左移,最后再全部相加。所以在对单个结果位的处理中要考虑到三个因素:第一个是当前的计算结果;第二个是前一位产生的进位;第三个是之前的计算中在这一位得出的结果。 除法在竖式运算中可以理解为是多次的减法。下图展示了除法算法的流程: 模指数运算 除此之外,还有多精度数的模指数运算,即计算以下式子的值: $$\Large{a^e\space mod\space m} $$ 可采用重复平方乘算法来实现: 算法实现 理解了竖式计算的流程与规则后,就可以使用算法进行实现了。由于课程实验原因,我做了Java和Python两个语言的版本,其中Java里面使用了ArrayList对数进行存储,Python中则使用了列表List进行存储。 Java: // 导入对应模块 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class BigNum { /** * 此方法用于快速创建一个存储有多精度整数的ArrayList对象 * 参数 elements 为整个整数的每一位数字 * 返回 ArrayList<Integer> */ public static ArrayList<Integer> createArrayList(int ... elements) { ArrayList<Integer> list = new ArrayList<Integer>(); for (Integer element : elements) { list.add(element); } return list; } /** * 此方法用于比较两个数的大小。若第一个数大于等于第二个数则返回true,否则返回false * 参数 num1, num2 为要比较的数 * 返回比较结果 boolean */ public static boolean isBigger(ArrayList<Integer> num1, ArrayList<Integer> num2) { if(num1....

Nov. 10, 2019 · 6 min · 1088 words