有限域下多项式计算的有关困惑

[Xor0v0]

有限域下多项式计算的有关困惑

0x01 背景

学习有限域下多项式运算遇到如下计算：
在有限域 $GF(2^8)$ 中，考虑多项式 $f(x)=x^6+x^4+x^2+x+1$ 和 $g(x)=x^7+x+1$ ，有：
$f(x)+g(x)=x^7+x^6+x^4+x^2 $
$f(x)\times g(x)=x^7+x^6+1 $

0x02 问题

• 在 $GF(p^n)$ 多项式模运算中，为啥系数模 $p$ 不模 $p^n$
• 有没有对于 $GF(p^n)$ 中的多项式的模运算的python脚本观摩一下以增进理解？或者标准库函数？

[Demian101]

感谢沉淀 github，蹲一个大佬来 Answer & 领取未来 Bounty

[yann-sjtu]

问题1

我觉得这只是一种定义。

$GF(p)$ 是定义在自然数域上的，且 p 必须为素数，否则该集合中的很多元素无法求模逆，也就不能构成一个域。
按照 $GF(p)$ 的定义， $p^n$ 不是素数，因此 $GF(p^n)$ 不能在自然数集合上形成一个域。因此需要构造一种新的代数结构，使得一个集合中包含 $p^n$ 个元素，且能够满足加减乘除运算。因此构造

$$ h(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_1x+a_0 $$

其中每个 $a_i$ 的取值范围为[0,p-1]，则 $h(x)$ 就有 $p^n$ 种不同的取值。这些所有多项式组成一个集合 $S$ 。

要定义一个有限域，除了定义一个集合，还需要定义加法和乘法运算(减法和除法相当于加法和乘法的模逆)。

对于所有 $f(x) \in S 且 g(x) \in S$ ，只有满足 $f(x)+g(x) \in S 且 f(x)*g(x) \in S$ ，则 $S$ 才能构成一个域(封闭性)，于是需要重新定义多项式的加法和乘法。

如问题所述的 $f(x)$ 和 $g(x)$ ，若想 $f(x)+g(x) \in S$ ，则只需要将多项式加法定义为系数模 p 即可。
而若想 $f(x)*g(x) \in S$，由于多项式乘法会出现更高次项，最高可能出现 $x^{2n-2}$ 。为了使得乘法结果仍然属于 $S$ ，只需要将乘法结果模一个n-1 次多项式 $m(x)$ 即可，于是便完成了 $GF(p^n)$ 的构造。

不同的 $m(x)$ 构造出的有限域也是不同的。至于如何选择 $m(x)$， 以及其他更详细的内容参考 http://stuyang.com/blog/763a052576b9/