信息论与编码基础知识有限域课件.ppt

有限域部分 1.1 整数的可除性 定义1.1 定理1.1 最大公因数和最小公倍数 定义1.3 最大公因数的一些性质： 最大公因数的一些性质： 定义1.4 性质 定义1.6 定义1.7 定理1.3 欧几里德算法 定理1.5 结论 1.2 同余式和欧拉-费尔马定理 整数按模运算 整数按模运算的一些性质： 定义1.8 同余式的主要性质： 例1.1 定义1.9 mod n剩余系的重要性质： 定义1.10 剩余缩系的一些性质： 定义1.11 引理1.1 引理1.2 定理1.8 定理1.9 定理1.9 推论1.1 1.3 群的基本概念 定义1.13 结论 群的一些性质： 定义1.14、15 有限群的一些性质： 定义1.18 循环群的主要性质： (3)若b∈aH,则aH=bH.即aH可以由其中任一个元所确定. 证明 若b∈aH,可以设b=ah1, h1∈H, (1.3.19) 对于bH中任一个元x,设x=bh2, h2∈H, (1.3.20) 于是x=bh2=a(h1h2)∈aH,这就是说,当b∈aH时,任意x∈bH,都有x∈aH,因此bH aH, (1.3.21) 由(1.3.19)式得到a=bh1-1 ∈bH,由上面证明结论可知aH bH, 于是 aH=bH. 证明： 例1.13 1.6.3 Fp[x]中多项式的性质 1.7 欧拉-费尔马定理的推广 定理1.18 1.7.2 模n剩余系的推广 定理1.32 定义1.33 例1.14 定理1.19 1.7.3 欧拉-费尔马定理的推广 推论1.3 例1.16 1.8 多项式的周期和本原多项式 定义1.35 引理1.6 由假设知xm-1∣xn-1，又xm-1可以整除（1.8.6）式等号右边第一项，因此xm-1∣xr-1，但0≦rm,只有r=0，即m∣n. 如果m∣n，设n=mq，于是 例1.17 定义1.36 例1.20 Fp[x]中的一个n次可约多项式的欧拉函数Φ(f(x))pn-2,因而它的周期也一定满足epn-2. 如果Fp[x]中的一个n次多项式的周期为pn-1,它一定是本原多项式，因为它是一个n次不可约多项式 若f(x)是Fp[x]中的一个n次不可约多项式，它的周期却不一定是pn-1，即它不一定是本原多项式。 一个n次不可约多项式，如果它的周期小于pn-1，则称它为非本原多项式。 例1.21 1.9 Fp[x]mod f(x)的同余类环 1.9.1 Fp[x]mod f(x)的同余类环的概念 在Fp[x]中任取一个n（n≥1）次多项式f(x) f(x)=xn+an-1xn-1+…+a1x+a0， (1.9.1) Fp[x]中多项式用f(x)去除，得到余式是一个次数小于n的多项式 b(x)=bn-1xn-1+bn-2xn-2+…+b1x+b0， (1.9.2) 其中bi∈Fp,每个bi可以独立的取0，1，…，p-1，组合起来得到全部余式，共有pn个，它们彼此modf(x)都不同余，且Fp[x]中每个多项式都必与（1.9.2）中某个多项式modf(x)同余，且仅与其中一个同余。 我们用这pn个余式作一个新集合，为此，引进一个新的符号α ，即用α代替b(x)中的x，这样得到pn个α的多项式： b(α)=bn-1 α n-1+bn-2 α n-2+…+b1 α +b0， (1.9.3) 例 1.22 取定F2[x]中一个多项式 f(x)=(x2+x+1)(x3+x2+1)=x5+x+1则同类余环Fp[x]/(f(x))中由32个元组成 F2[x]/(f(x))={a4 α 4+a3 α 3+…+a1 α +a0︱ai∈F2}下面看F2[x]/(f(x))中的运算。例如b1(α）= α3+ α 2+1，b2(α)= α 4+ α 2+ α ，因为 b1(x)+b2(x) ≡ x4+x3+x+1 modf(x),因而b1(α)+b2(α)= α 4+ α 3+ α +1，又因为 b1(x)b2(x) ≡ x4+x2+x+1 modf(x)，因而b1(α)b2(α)= α 4+ α 2+ α +1.如果我们取 b′1(α)= α 2+ α +1,