作业 6：有限域、周期与纠错码（12 月 5 日）

#作业

题面由课程教材与我当时提交的 8 页手写作答核对恢复。我在第一道大计算题处明确写了“不会”，下文保留这一事实，并补上可复习的方法。

第 1 节第 1 题：两个九元域

验证 x2+1x^2+1 与 x2+x+2x^2+x+2 在 F3[x]\mathbb F_3[x] 中不可约；写出

F3[x]/(x2+1),F3[x]/(x2+x+2)\mathbb F_3[x]/(x^2+1), \qquad \mathbb F_3[x]/(x^2+x+2)

的加法表、乘法表，并找出两域之间的同构。

展开作答

我当时在此题写的是“不会”。补充解析如下。

两个二次多项式在 0,1,20,1,2 处都不为零，所以不可约，对应商环都是九元域。每个元素唯一写成 a+bαa+b\alpha，a,b∈F3a,b\in\mathbb F_3；加法逐系数模 3，乘法后分别用

α2=−1=2\alpha^2=-1=2

或

β2=−β−2=2β+1\beta^2=-\beta-2=2\beta+1

降次，这两条规则就完整决定了两张 9×99\times9 运算表。

在第二个域中，(β+2)2+1=0(\beta+2)^2+1=0。因此映射

a+bα⟼a+b(β+2)a+b\alpha\longmapsto a+b(\beta+2)

是从第一个域到第二个域的同构。

第 1 节第 2 题：枚举低次不可约多项式

列出 F2[x]\mathbb F_2[x]、F3[x]\mathbb F_3[x] 中全部二次、三次首一不可约多项式，并各给出两个四次不可约多项式；据此构造 22,23,242^2,2^3,2^4 元域。

展开作答

F2\mathbb F_2 上：

  • 二次：x2+x+1x^2+x+1；
  • 三次：x3+x+1x^3+x+1、x3+x2+1x^3+x^2+1；
  • 四次示例：x4+x+1x^4+x+1、x4+x3+1x^4+x^3+1。

F3\mathbb F_3 上二次首一不可约多项式为

x2+1,x2+x+2,x2+2x+2.x^2+1,\quad x^2+x+2,\quad x^2+2x+2.

三次首一不可约多项式可通过检查在 0,1,20,1,2 均无根来枚举；我当时列出了八个，方法比死背列表重要。四次还要进一步排除两个不可约二次式的乘积。

选取相应次数的不可约多项式 fnf_n，即可构造

F2n≅F2[x]/(fn),n=2,3,4.\mathbb F_{2^n}\cong\mathbb F_2[x]/(f_n),\qquad n=2,3,4.

第 1 节第 5 题：整除关系

设 d∣md\mid m，证明：

pd−1∣pm−1,p^d-1\mid p^m-1, xpd−x∣xpm−x.x^{p^d}-x\mid x^{p^m}-x.
展开作答

令 m=kdm=kd。第一式来自等比数列分解：

pm−1=(pd)k−1=(pd−1)∑j=0k−1pdj.p^m-1=(p^d)^k-1=(p^d-1)\sum_{j=0}^{k-1}p^{dj}.

对第二式，xpd−xx^{p^d}-x 的根恰是 Fpd\mathbb F_{p^d} 的全部元素。因为 d∣md\mid m，Fpd\mathbb F_{p^d} 是 Fpm\mathbb F_{p^m} 的子域，所以这些元素也全是 xpm−xx^{p^m}-x 的根。两边都无重根，故前者整除后者。

第 1 节第 6 题：任意生成元吗

若 Fpn=Fp(α)\mathbb F_{p^n}=\mathbb F_p(\alpha)，问 α\alpha 是否一定生成乘法群 Fpn×\mathbb F_{p^n}^\times？

展开作答

不一定。“生成整个域”只要求 α\alpha 不落在真子域；“生成乘法群”则要求 o(α)=pn−1o(\alpha)=p^n-1，条件更强。

反例取 F9=F3[x]/(x2+1)\mathbb F_9=\mathbb F_3[x]/(x^2+1)，令 α=xˉ\alpha=\bar x。它确实生成域，但 α2=−1\alpha^2=-1，所以 o(α)=4o(\alpha)=4，而 ∣F9×∣=8|\mathbb F_9^\times|=8，并非乘法群生成元。

第 2 节第 1 题：九元域的乘法群

验证 F3[x]/(x2+1)\mathbb F_3[x]/(x^2+1) 的非零元乘法群是循环群并找出生成元；判断 x2+1x^2+1 是否为本原多项式。

展开作答

令 α=xˉ\alpha=\bar x。计算可得 α+2\alpha+2 的连续幂遍历全部 8 个非零元素，因此它是生成元。可是 α4=1\alpha^4=1，α\alpha 本身阶为 4，不是乘法群生成元。故 x2+1x^2+1 虽不可约，却不是本原多项式。

第 2 节第 2 题：判断本原多项式

判断 x3+x+1x^3+x+1、x4+x+1x^4+x+1 是否为 F2[x]\mathbb F_2[x] 中的本原多项式。

展开作答

二者都是。

x3+x+1x^3+x+1 不可约，其周期整除 23−1=72^3-1=7，且不为 1，因此周期只能是 7。

x4+x+1x^4+x+1 不可约，周期整除 1515。分别检查它不整除 x1−1x^1-1、x3−1x^3-1、x5−1x^5-1，排除 1、3、5，故周期为 15。

第 2 节第 3 题：Frobenius 自同构

证明

φ:Fpm→Fpm,a↦ap\varphi:\mathbb F_{p^m}\to\mathbb F_{p^m},\qquad a\mapsto a^p

是自同构，并固定素子域 Fp\mathbb F_p 中的每个元素。

展开作答

特征 pp 下“新生儿之梦”给出

(a+b)p=ap+bp,(ab)p=apbp,(a+b)^p=a^p+b^p,\qquad (ab)^p=a^pb^p,

所以 φ\varphi 是域同态。域同态的核只能是 0，因此单射；有限集合上的单射必满射，所以它是自同构。对 a∈Fpa\in\mathbb F_p，Fermat 定理给出 ap=aa^p=a，故逐点固定素子域。

第 2 节第 7 题：在 F34\mathbb F_{3^4} 中计算

设 α\alpha 是 x4+x+2x^4+x+2 的根。写出 F3(α)\mathbb F_3(\alpha) 的一般元素，并计算

1+α+α31+α2+α3+α+α2.\frac{1+\alpha+\alpha^3}{1+\alpha^2+\alpha^3}+\alpha+\alpha^2.
展开作答

一般元素唯一写成

a0+a1α+a2α2+a3α3,ai∈F3.a_0+a_1\alpha+a_2\alpha^2+a_3\alpha^3, \qquad a_i\in\mathbb F_3.

教材给出的关键恒等式是

α2(α3+α2+1)=1.\alpha^2(\alpha^3+\alpha^2+1)=1.

因此分母的逆元为 α2\alpha^2。代入并用 α4=−α−2\alpha^4=-\alpha-2 降次，结果为

α3+α2+2α.\alpha^3+\alpha^2+2\alpha.

第 2 节第 9 题：七位循环码

在 F2[x]\mathbb F_2[x] 中取本原多项式 g(x)=x3+x+1g(x)=x^3+x+1，把次数小于 7 的多项式与七位向量对应，并令码集合由 g(x)g(x) 的倍数组成。

  1. 对 f(x)=x6+x4+c1x2+c2x+c3f(x)=x^6+x^4+c_1x^2+c_2x+c_3，确定 c1,c2,c3c_1,c_2,c_3 使 f∈Mf\in M；
  2. 对收到的
f1=x6+x5+x4+x3+x2+x+1,f_1=x^6+x^5+x^4+x^3+x^2+x+1, f2=x6+x4+x3+x2+x+1,f_2=x^6+x^4+x^3+x^2+x+1,

在至多一位出错的前提下译码。

展开作答

第一问把 x6+x4x^6+x^4 除以 g(x)g(x)，余数为 x+1x+1，因此取

c1=0,c2=1,c3=1.c_1=0,\qquad c_2=1,\qquad c_3=1.

第二问中，f1=(x3+x2+1)g(x)f_1=(x^3+x^2+1)g(x)，没有错误。

f2f_2 除以 gg 的余数为 x2+x+1x^2+x+1。继续计算各单项式的伴随式可得

x5≡x2+x+1(modg(x)),x^5\equiv x^2+x+1\pmod{g(x)},

所以错在 x5x^5 位。纠正后的码字为

f2+x5=x6+x5+x4+x3+x2+x+1.f_2+x^5=x^6+x^5+x^4+x^3+x^2+x+1.

评论