有限域的基本概念和质数、不可分解多项式的搜寻算法

关于有限域的两个有趣应用的旧文，排个版重发。

有限域的概念

有限域（Finite Field）在数学上属于群论（Group Theory）的范畴，又称伽罗瓦域（Galois Field）。简单来说，就是包含有限个元素的域。例如GF（2^8）这个AES加密算法中涉及的有限域，包含了256个元素。在这个有限域中可以定义乘法和加法操作，那么这256个元素中的乘积和加和都不能超出这256个元素的范围。

有限域的多项式表示

表示有限域中元素的一种方式是多项式。例如GF（2^2）中的所有四个元素，可以用{0，1，x，x+1}四个多项式来表示，而且需要注意到这些多项式系数不是1就是0，这样多项式中的每一个degree项就对应了二进制的每一个bit的权重，而系数就对应了这个bit的具体取值。

有限域中的运算

那么元素的加法，可以用对应多项式的系数的加法来表示，通常定义成对应系数的异或操作。元素的乘法呢，先采用普通的算术乘法。这样就会出现x*(x+1)=x^2+x，这样的结果是超出了GF(2^2）的范围。为了使这个结果回到有限域的范围，需要再对这个算术积做一次模运算（modulo）。模运算其实就是选择一个特殊的除数，和算术积做除法，然后取余数作为模运算的结果。做模运算的除数多项式称之为 reduction polynomial。

有限域中的不可分解多项式

这个reduction polynomial必须是一个不可分解的多项式（prime reduction polynomial）。如果可以分解，那么模运算的结果就会出现0（即算术积可以被整除），这在有限域中是不允许出现的。所以找到有限域中的prime reduction polynomial，就成为完成该有限域中的乘法和加法定义的关键步骤。

质数搜索算法

微软一位工程师的博客[1]上介绍了一种方法，称之为A Sieve of Eratosthenes method。这种方法可以用于搜寻质数（素数，primes），理解了搜寻质数的算法原理，那么就可以同样用这种方法来搜寻不可分解多项式了。

所以首先看一下如何搜寻质数。用这种方法搜寻不超过某个正整数N的所有质数的原理大概是这样子的：

1.先把这N个整数都列出来，首先把1划掉，因为1很特殊，但我们知道1不是质数。首先把这N-1个数都标记为质数（假设）。2.从最小的质数2开始，把不大于N的该质数所有倍数2、3、4、。。。都标记为合数（非质数）。3.从下一个质数开始，重复步骤2，直到最后一个质数。4.那么N-1个整数的质数和合数就都分别得到了正确的标记。

这种方法的原理比较直白，如果一个正整数N是合数，那么在前面的N-2轮Sieving中，肯定会被标记为合数。否则，开始它的假设标记是质数，就是成立的。这种方法看起来只适合寻找比较小的质数，如果质数很大，需要的计算次数就是海量的了，实际不太可行。

质数搜索算法的改进

仔细研究的话，上面描述的方法中有很多步骤是冗余的，可以精简。例如步骤2在用程序实现算法时，本来是个从2到N的循环。但是从2开始没有必要，可以从当前质数的平方开始，直到N循环结束。因为当前质数为2时，可以看出，4、6、8将被标记为合数。这样下一个质数3的倍数循环中，可以直接从9开始循环，前面的6已经没有必要再次计算了。质数越大，减少的计算次数越多。

另外，因数中有2的合数在第一次循环中就都已经被标记为合数了。后面开始下一个质数的循环时，倍数可以跳过偶数倍，只用奇数倍。

质数搜索算法的TCL源代码

作者用数字前端工程师最爱的TCL脚本分别实现了原版和简化版的代码，放在了作者的github[2]，感兴趣的可以看看。不过没有怎么关注计算时间的比较。点击阅读原文也可以跳转过去。

好吧。到这里就可以继续之前的搜寻不可分解多项式的问题了。

不可分解多项式的搜索算法

前面说到搜寻质数的一个算法，其实就是先把一定范围内的整数都列出来，然后从小到大，按一定的遍历顺序计算乘积，然后把对应该乘积的整数标记为合数。计算到最后，剩下的就是质数了。背后的原则就是一个合数肯定是由比它小的两个数相乘得来的。

这个原则同样可以推广到搜寻有限域的不可分解多项式。把一定范围的（通常是不高于N阶）多项式全部列出来，从阶数最小的多项式开始遍历计算乘积，把结果标记为可分解多项式，最后剩下的就是不可分解多项式。

不可分解多项式搜索算法的TCL源代码

用程序实现这个过程，首先要实现基本的几个操作。例如多项式的加法和乘法操作。加法比较简单，就是对应项系数做个异或。乘法就是移位和加法。另外，为了方便遍历，把每个多项式都对应成一个整数，在每一个循环过程中，把当前的整数转换回多项式，进行乘法操作。具体的实现可以参考TCL脚本中的各个PROC子过程。相关源码仍放在作者的github[3]。

有同学说琢磨这些有啥用，我竟无言以对，也许是补补小时候的奥数课吧哈哈。其实也就是个兴趣，解开心中的一个疑惑，不亚于跑个五公里所分泌的多巴胺带来的快感。记录更多的是为自己，而不是为了传播。

常怀好奇之心，常怀感恩之心，与诸君共勉。

References

[1] 微软一位工程师的博客: https://blogs.msdn.microsoft.com/matthew_van_eerde/2011/11/11/generating-primes-using-the-sieve-of-eratosthenes-plus-a-few-optimizations/ [2] github: https://github.com/hanjingfei/tcl.primes [3] github: https://github.com/hanjingfei/tcl.poly_sieve