2022-06-05 09:59 门头沟学院芯片研发

关注

密码学数学基础之有限域基础

有一类特殊的环具有比较好的运算性质：可以进行加、减、乘、除四则混合运算，这就是域。包含有限个元素的域称为有限域，在密码学中有着非常广泛的用途。

本文介绍有限域的基本结构和构造方法。

重要前置知识

一个重要的定理：如果p是素数，则剩余类环 $Z_{p}$ 是一个域，若n是合数，则剩余类环 $Z_{n}$ 有零因子，不是域。

我们已经得到了一种特殊类型的有限域： $Z_{p}$ 。

这种有限域可以用来作为构造密码算法的基础，但是有些时候不够，还需要寻找更多类型的有限域。

包含q个元素的有限域用 $F_{q}$ 或者 $GF(q)$ 来表示。

例子：

$GF(2), GF(3), GF(4)$ 的加法表和乘法表。

多项式

定义1 数域F上的多项式指的是具有如下形式的表达式：
$f(x)=f_{n}x^{n}+f_{n-1}x^{n-1}+...f_{1}x+f_{0}$

其中x称为未定元， $f_{i}x^{i}$ 称为i次项， $f_{0},f_{1},...,f_{n}$ 称为多项式的系数，所有系数均取自于数域F。未定元x的最高次的系数 $f_{n}$ 不等于0，称n为多项式 $f(x)$ 的次数，记作 $deg f$ 。

比如 $5x^{3}+4x^{2}+1$ 是有理数域上的3次多项式： $(1+i)x^{6}-2x^{3}+i$ 是复数域上的6次多项式。

多项式环

数域F上的全体多项式在多项式的加法和乘法下构成了一个环，称为F上的多项式环，记作 $F[x]$ ，F称为系数域。

当n等于0时多项式 $f(x)$ 是数域F中的一个数，特别地， $f(x)=0$ 称为零多项式。一般将 $f_{n}x^{n}$ 称为多项式 $f(x)$ 的首项，如果 $f_{n}=1$ ，则 $f(x)$ 称为首一多项式。

比如： $x^{3}-\pi x^{2}+1$ 是实数域上的3次首一多项式。
定义2 设 $a(x)、r(x)、s(x)、p(x)$ 都是数域F上的多项式，则当 $a(x)r(x)=s(x)$ 且 $r(x)$ 不是零多项式时，称 $r(x)$ 整除 $s(x)$ ， $s(x)$ 称作 $r(x)$ 的倍式， $r(x)$ 是 $s(x)$ 的因式，记作 $r(x)|s(x)$ 。

带余除法：对于任意一对多项式 $c(x)$ 和 $d(x)$ ，其中 $d(x)$ 不是零多项式，则一定存在唯一的一对多项式 $Q(x)$ 和 $r(x)$ ，使得 $c(x)=Q(x)d(x)+r(x)$ 。

其中 $r(x)$ 的次数小于 $d(x)$ 的次数， $Q(x)$ 称为商多项式， $r(x)$ 称为余多项式。
这个时候我们也称 $c(x)$ 模 $d(x)$ 等于 $r(x)$ 。

最大公因式

定义3 两个多项式 $r(x)$ 、 $s(x)$ 的最大公因式指的是满足下面两个条件的首一多项式 $u(x)$ ：

$u(x)$ 是 $r(x)$ 和 $s(x)$ 的公共因式，即 $u(x)|r(x)$ 且 $u(x)|s(x)$ 。
若 $v(x)$ 是 $r(x)$ 和 $s(x)$ 的公共因式，则一定有 $v(x)|u(x)$ 。

求两个多项式的最大公因式有一个标准的算法，我们称为多项式的欧几里得算法，或者辗转相除法。其过程完全类似于求两个整数的最大公因子。

欧几里得算法

给定两个多项式 $c(x)$ ， $d(x)$ ，且 $c(x)$ 的次数不小于 $d(x)$ 的次数，利用多项式的带余除法可得：

每一个余多项式的次数都严格小于除多项式的次数，所以在进行有限步带余除法以后一定会得到余多项式为0。
最终计算出的 $r_{n}(x)$ 就是 $c(x)$ 和 $d(x)$ 的最大公因式。
两个多项式的最大公因式也可以表示成它们的组合。给定 $F[x]$ 中的两个多项式 $c(x)$ 和 $d(x)$ ，一定存在 $F[x]$ 中的多项式 $u(x)$ 和 $v(x)$ ，使得 $c(x)$ 和 $d(x)$ 的最大公因式等于 $u(x) c(x)+v(x)d(x)$ 。
求多项式 $u(x)$ 和 $v(x)$ 也有一个标准的算法，仍然叫做扩展的欧几里得算法。

定义4 若两个多项式的最大公因式为1，则称它们互素。

定理1 $F[x]$ 中两个多项式 $c(x)$ 和 $d(x)$ 互素的充分必要条件是存在 $F[x]$ 中的多项式 $u(x),v(x)$ ，使得 $u(x)c(x)+ v(x)d(x)=1$ 。

定义5 若数域F上的多项式 $p(x)$ 只能被 $α$ 或者 $αp(x)$ 整除，其中 $α$ 是数域 $F$ 中的非零元，则称 $p(x)$ 为不可约多项式，否则称为可约多项式；次数至少为1的首一不可约多项式称为素多项式。

例1 二次多项式 $f(x)=x^{2}+1$ 在实数域内是不可约多项式，但是在复数域内是可约的。

定理2（唯一因式分解定理）数域F上的任意非零多项式 $f(x)$ 都可以唯一分解为一个常数乘以数域F上的若干素多项式的乘积，即 $f(x)=cp_{1}^{r_{1}}(x)cp_{2}^{r_{2}}(x)...cp_{s}^{r_{s}}(x)$ 。

其中 $c$ 是数域 $F$ 中的常数， $p_{i}(x)$ 为F上的素多项式， $r_{i}$ 为正整数。

多项式模p(x)环

定义6 设 $p(x)$ 是域F上次数非零的首一多项式，则F上次数小于 $p(x)$ 的多项式全体对于多项式的加法和模 $p(x)$ 乘法构成一个环，称为多项式模 $p(x)$ 环。

定理3 多项式模首一多项式 $p(x)$ 环成为域的充分必要条件是 $p(x)$ 为素多项式。

证明充分性：若 $p(x)$ 为素多项式，则环中任意非零多项式 $s(x)$ 与 $p(x)$ 互素，存在一组多项式 $a(x)$ 和 $b(x)$ ，使得 $a(x)p(x)+b(x)s(x)=1$ 。

等式两端同时模 $p(x)$ ，则 $b(x)s(x)$ 在模 $p(x)$ 运算下是等于1的， $b(x)$ 是 $s(x)$ 的逆元。
必要性用反证法，设 $p(x)$ 不是素多项式，则可以分解为次数较低的两个非零多项式的乘积 $p(x)=r(x)s(x)$ ，等式两边同时乘以 $r(x)$ 的逆并取模 $p(x)$ ，可以得到 $s(x)=0$ ，导出矛盾。因此 $p(x)$ 是素多项式。