有限域上的多项式优化

定义6.17 系数取自GF（q）上的x的多项式称为有限域上的多项式，表示为

当f（x）的系数均为零时，称其为零多项式，用0表示；若f（x）是n次多项式，则记为∂f（x）=n或deg f（x）=n，规定∂0=-∞；全体GF（q）上的x的多项式集合记为F_q[x]或GF（q）[x]。

定义6.18 首项系数为1的多项式称为首一多项式。

有限域上多项式的相等与加法和乘法运算规则与普通代数多项式相同。特别地，对于GF（2）上的多项式，因为是模2运算，加与减相同，故有xⁱ+xⁱ=0，f_i+f_i=0，f_i²=f_if_i=f_i。

可以验证，全体GF（q）上的x的多项式集合F_q[x]构成一个交换环。

定义6.19 在GF（q）上次数大于零的多项式f（x），若除了常数和常数与本身的乘积以外，不能再被GF（q）上的其他多项式除尽，则称f（x）为GF（q）上的既约多项式（或不可约多项式）。

由定义知，一个非零常数总是多项式的因子；不论在哪一个域上，一次多项式都是既约多项式；多项式f（x）是否是既约的，与讨论的域关系很大。

【例6.12】

给定f（x）=x²+1，则在实数域R上f（x）是既约的；在复数域上f（x）=（x+i）（x-i），是可约的。在GF（2）上f（x）=（x+1）（x+1），也是可约的。

与整数的唯一分解定理类似，有限域上的多项式也有相应的性质存在。(www.xing528.com)

定理6.9 首一多项式f（x）必可以分解为首一既约多项式之积，并且当不考虑因式的顺序时，这种分解是唯一的，即

式中，p_i（x）（i=1，2，…，s）是首一既约多项式；α_i（i=1，2，…，s）是正整数。

定义6.20 设f（x）∈F_q[x]，若x=β时有f（β）=0，则称β为多项式f（x）的一个零点或根。

定理6.10 β为多项式f（x）的根的充要条件是（x-β）f（x）。

定理6.11 n次多项式f（x）至多有n个根。

定义6.21 同时能够除尽多项式a（x），b（x），…，f（x）的次数最高的首一多项式，称为这一组多项式的最大公因式，记为（a（x），b（x），…，f（x））或GCD（a（x），b（x），…，f（x））。

定义6.22 同时能够被多项式a（x），b（x），…，f（x）除尽的次数最低的首一多项式，称为这一组多项式的最小公倍式，记为[a（x），b（x），…，f（x）]或LCM（a（x），b（x），…，f（x））。

GF（q）上全体多项式集合F_q[x]与全体整数集合Z均构成一个交换环，可以验证，多项式理论与整数理论是完全平行的。多项式相当于一般的整数；既约多项式相当于素数，非既约多项式（可约多项式）相当于合数；而常数（零次多项式）相当于整数中的1，它既不是既约多项式，也不是可约多项式；多项式的最大公因式和最小公倍式与整数的最大公因数和最小公倍数相似。多项式与整数的这种平行关系，在下面的讨论中还将看到。