伽罗华（法国，1811～1832）才华横溢，可惜在21岁时早早死于情场决斗。他证明了：对于给定的一个素数次不可约方程能判断出它是否能根式求解。
Bluetooth在bit streaming过程中计算Sync word，HEC，FEC及data whitening时使用到了伽罗华域中的计算规则来处理比特流，本文就收集到的信息做个总结。
一个元素个数有限的域称为有限域，或者伽罗华域(Galoisfield)
- 有限域中元素的个数为一个素数，记为GF(p),其中p为素数;
一个大于1的整数，如果它的正因数只有1和它本身，就叫做素数，否则就叫做合数
有限域中运算满足
– 交换律:a+b = b+a, a·b = b·a
– 结合律:(a+b)+c = a+(b+c), a·(b·c) = (a·b)·c
– 和分配律:a·(b+c) = a·b+a·c将GF(p)延伸为一个含有$p^m$个元素的域，称为GF(p)的扩展域，表示为GF($p^m$)，m是一个非零正整数。
注意:GF(p)是GF($p^m$)的子集。
二进制域GF(2)是扩展域GF($2^m$)的一个子域，类似于实数域是复数域的一个子域一样。除了数字0和1之外，在扩展域中还有特殊的元素，用一个新的符号a表示。GF($2^m$)中任何非0元素都可由a的幂次表示。
有限元素的集合GF($2^m$)，只能含有$2^m$个元素，并且对乘法封闭，其约束条件为$a^{(2^m−1)}$+1=0
• 根据这个多项式限制条件，任何幂次等于或超过$2^m-1$的域元素都可降阶为下述幂次小于$2^m-1$的元素:
这样，GF($2^m$)的元素可表示为:
扩展域$GF(2^m)$中的加法
• 在$GF(2^m)$中，将每个非0域元素用多项式$a_i(x)$表示，其系数至少有一个不为0。对于i=0,1, 2,…,$2^m-2$，有:
• 先看m=3,有限域表示为$GF(2^3)$,下表为上式描述的基本元素(Primitive Element) ${x^0,x^1,x^2}$映射为7个元素{$a_i$}和一个0元素。表中的各行是二进制数字序列，代表上式中的系数$a_{i,0}、a_{i,1}、a_{i,2}$的取值。
| _ | $x^0$ | $x^1$ | $x^2$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| $a^0$ | 1 | 0 | 0 |
| $a^1$ | 0 | 1 | 0 |
| $a^2$ | 0 | 0 | 1 |
| $a^3$ | 1 | 1 | 0 |
| $a^4$ | 0 | 1 | 1 |
| $a^5$ | 1 | 1 | 1 |
| $a^6$ | 1 | 0 | 1 |
| $a^7$ | 1 | 0 | 0 |
多项式$f(x)=1+x+x^3$ 为GF($2^3$)的元素与基本元素之间的映射。
有限域中两个元素的加法定义为两个多项式中同幂次项系数 进行模2加，即
$a^i+a^j=(a_{i,0}+a_{j,0}) + (a_{i,1}+a_{j,1})x + … + (a_{i,m-1}+a_{j,m-1})x^{m-1}$
• 有限域的本原多项式。本原多项式定义了域GF($2^m$)， 一个多项式是本原多项式的充要条件:
一个m阶的不可约多项 式f(x)，如果f(x)整除$x^n+1$的最小正整数n满足$n=2^m-1$，则该多项式是本原的。
关于多项式在伽罗华域的求根
以$p(x) = 1 + x + x^3$ 为例，多项式的幂次为m=3,所以由p(x)所定义的域中包含了$2^m=2^3=8$个元素。求解p(x)的根就是指找到x 使p(x)=0。由高斯的基本代数学理论我们知道，对于幂次为m的多项式必然有m个根。对于这个例子，p(x)=0有3个根，由于这3个根不可能位于与p(x)系数相同的有限域中，而是位于扩展域GF($2^3$)中。
用扩展域的元素 a来定义多项式p(x)的根，可写成如下形式:p(a)=0
即 $1+a+a^3=0$，在该多项式两边都加上 1 + a, 就可以得到$a^3=1+a$ 这意味着$a^3$可以表示为更低阶a项的加权和。
类似地有:
$a^4$=a$a^3$=a(1+a)=a+$a^2$
$a^5$=a$a^4$=a(a+$a^2$)=$a^2$+$a^3$=1+a+$a^2$
$a^6$=a$a^5$=a(1+a+$a^2$)=a+$a^2$+$a^3$=1+$a^2$
$a^7$=a$a^6$=a(1+$a^2$)=a+$a^3$=1=$a^0$
所以，有限域GF($2^3$)的8个元素为 ${0,a^0,a^1,a^2,a^3,a^4,a^5,a^6}$
这8个元素中哪些是p(x)=0的3个根呢?我们可通过枚举 找到!
p($a^0$)=1, $a^0$不是
p($a^1$)=1+a+$a^3$=0, $a^1$是
p($a^2$)=1+$a^2$+$a^6$=1+$a^0$=0, $a^2$是
p($a^3$)=1+$a^3$+$a^9$=1+$a^3$+$a^2$=1+$a^5$=$a^4$, $a^3$不是
p($a^4$)=1+$a^4$+$a^12$=1+$a^4$+$a^5$=1+$a^0$=0, $a^4$是
同理可计算p($a^5$)、p($a^6$)都不等于0，所以p(x)=1+x+$x^3$的 3个根是a, $a^2$, $a^4$
主要参考文献有
FEC的介绍