Matlab中的有限域计算

Matlab中的有限域计算在这篇文章中,我们先简单介绍有限域的基础知识,然后介绍Matlab中几个与有限域计算相关的函数.

1 有限域基础知识

1.1 有限域(Galois域)的构造

p 为一个素数. 则对任意的一个正整数

n
,存在一个特征为 p ,元素个数为

pn
的有限域 GF(pn) .

注:任意一个有限域,其元素的个数一定为 pn ,其中 p 为一个素数(有限域的特征),

n
为一个正整数.

例1(有限域 GF(p) p 为一个素数,集合



GF(p)=Zp={0,1,2,,p1}.





GF(p)
上定义加法


和乘法


分别为模

p
加法和模



p

乘法,即任意的

a,bGF(p)



ab=(a+b)modp, ab=(ab)modp





<GF(p),,> <script type=”math/tex” id=”MathJax-Element-638″> </script> 为一个有

p
个元素的有限域,其中零元素为



0

,单位元为

1
.



a
GF(p) 中的一个非零元素. 由于 gcd(a,p)=1 ,因此,存在整数 b,c ,使得 ab+pc=1 . 由此得到 a 的逆元为

a1=bmodp
.

GF(p) 称为一个素域(prime field).

例注1: 给定 a

p
,例1中的等式 ab+pc=1 可以通过扩展的欧几里得除法得到,从而求得 GF(p) 中任意非零元素的逆元.

例2(有限域 GF(pn) GF(p) 出发,对任意正整数 n

n2
,我们可以构造元素元素个数为 pn 的有限域 GF(pn) 如下:
g(x) 为一个 GF(p) 上次数为 n 不可约多项式,集合



GF(pn)=GF(p)[x]/g(x)={a0+a1x+a2x2++an1xn1 | aiGF(p),0in1}





GF(pn)
上定义加法


和乘法


分别为模

g(x)
加法和模

g(x)
乘法,即任意的

a(x),b(x)GF(pn)



a(x)b(x)=a(x)+b(x), a(x)b(x)=(a(x)b(x))modg(x)





<GF(pn),,> <script type=”math/tex” id=”MathJax-Element-671″> </script> 为一个有

pn
个元素,特征为

p
的有限域,其中零元素为



GF(p)

中的

0
,单位元为



GF(p)

中的

1
.



a(x)
GF(pn) 中的一个非零元素. 由于 gcd(a(x),g(x))=1 ,因此,存在 GF(p) 上的多项式 b(x),c(x) ,使得 a(x)b(x)+g(x)c(x)=1 . 由此得到 a(x) 的逆元为 a1(x)=b(x)modg(x) .

GF(pn) 称为 GF(p) 的( n 次)扩域(extension field),而

GF(p)
称为 GF(pn) 子域(subfield).

例注2.1: 给定 GF(p) 上的多项式 a(x) g(x) ,例2中的等式 a(x)b(x)+g(x)c(x)=1 可以通过扩展的欧几里得除法得到,从而求得 GF(pn) 中任意非零元素的逆元.

例注2.2: GF(q) 是一个含有 q 个元素的有限域. 对任意正整数

n
, GF(q) 上的 n 次不可约多项式一定存在. 更进一步,

GF(q)
上首项系数为 1

n
次不可约多项式的个数为

Nq(n)=1nd|nμ(nd)qd=1nd|nμ(d)qn/d



其中

μ
为Moebius函数,定义为


μ(m)=1(1)k0m=1m=p1p2pk,p1,p2,,pk

1.2 有限域的性质

GF(q) 是一个含有 q 个元素的有限域,

Fq=GF(q){0}
为有限域 GF(q) 中所有非零元素构成的集合. 则在乘法之下 Fq 是一个有限循环群. 循环群 Fq 的一个生成元称为有限域 GF(q) 的一个本原元.

αGF(q) 为一个本原元,则

GF(q)={
0,1,α,α2,,αq2}



并且

αq1=1
,即

αq=α
.

定义: GF(q) 是一个含有 q 个元素的有限域,

GF(p)
GF(q) 的一个含有 p 个元素的子域(

p
不一定为素数), αGF(q) . 则 GF(p) 上以 α 为根,首项系数为 1 ,并且次数最低的多项式称为

α
GF(p) 上的极小多项式(minimal polynomial of α over GF(p) ).

特别地,若 αGF(q) GF(q) 的一个本原元,则 α GF(p) 上的极小多项式称为 GF(p) 上的一个本原多项式(primitive polynomial for GF(q) over GF(p) ).

定义注1:对任意的 αGF(q) α GF(p) 上的极小多项式存在并且唯一,并且 α GF(p) 上的极小多项式为 GF(p) 上的一个不可约多项式.

定义注2: αGF(q) , 则 α αp GF(p) 上具有相同的极小多项式. 更进一步,集合

B(α)={
α,αp,αp2,αp3,,αpi,}



中的元素具有相同的极小多项式. 设

q=pn
,则

αpn=α
. 因此,集合

B(α)
中互不相同的元素的个数(记为

r
)不超过



n

. 可以证明,

α


GF(q)
的一个本原元当且仅当

r=n
.

定理: GF(q) 是一个含有 q 个元素的有限域,

GF(p)
GF(q) 的一个含有 p 个元素的子域. 设

αGF(q)
r 为满足

αpr=α
的最小正整数. 则 α GF(p) 上的极小多项式 g(x) 是一个 r 次不可约多项式,并且



B(α)={α,αp,αp2,,αpr1}



中的元素为

g(x)


GF(q)
上的所有不同的根,即


g(x)=(xα)(xαp)(xαp2)(xαpr1).

注: r 的计算方法如下:设

α
Fq 中的阶为 k . 集合



Zk={m | 0mk1,gcd(m,k)=1}



在模

k
乘法运算下是一个含有



φ(k)

个元素的有限群(其中

φ
为欧拉(Euler)函数). 则

r
等于



pmodk



Zk
中的阶.

推论: GF(q) 是一个含有 q 个元素的有限域,

GF(p)
GF(q) 的一个含有 p 个元素的子域. 设

|GF(q)|=pn
,即 q=pn . 设 αGF(q) GF(q) 的一个本原元,则 α GF(p) 上的极小多项式 g(x) 的次数为 n ,并且



g(x)=(xα)(xαp)(xαp2)(xαpn1).



更进一步,

α,αp,αp2,,αpn1
均为

GF(q)
的本原元.

注: GF(p) 是一个含有 p 个元素的有限域,

n
是任意一个正整数,则 GF(p) 上的 n 次本原多项式一定存在. 更进一步,

GF(p)
上的首项系数为 1

n
次本原多项式的个数为 φ(pn1)n ,其中 φ 为欧拉函数.

例3 考虑二元域 GF(2) 上的不可约多项式 p(α)=α3+α+1 ,构造有限域

GF(23)=GF(2)[α]/p(α)={
0,1,α,α+1,α2,α2+1,α2+α,α2
+α+1}.



容易验证,

α,α2,α3,α4,α5,α6
都是

GF(23)
的本原元.

GF(2)
上的首项系数为

1




3

次本原多项式有两个,分别为

(i)

α,α2,α4


GF(2)
上的极小多项式


g(x)=(x+α)(x+α2)(x+α4)=x3+x+1



(ii)

α3,α5,α6


GF(2)
上的极小多项式


g(x)=x3+x2+1

有限域 GF(p) 上的本原多项式一定是 GF(p) 上的不可约多项式;但是, GF(p) 上的不可约多项式不一定是 GF(p) 上的本原多项式.

定理: GF(q) 是一个含有 q 个元素的有限域,

GF(p)
GF(q) 的一个含有 p 个元素的子域,

g(x)
GF(p) 上的一个不可约多项式. 则 g(x) GF(p) 上的本原多项式当且仅当 g(x) GF(q) 上的根都是 GF(q) 的本原元.

下面例子说明不可约多项式不一定是本原多项式.

例4 考虑二元域 GF(2) 上的不可约多项式 p(x)=x4+x3+x2+x+1 ,构造有限域

GF(24)=GF(2)[x]/p(x)={
a+bx+cx2+dx3 | a,b,c,d
GF(2)}.



显然,

xGF(24)
. 由于

x5=1
,即

x
的阶为



5

,因此,

x
不是



GF(24)

的本原元. 于是,

p(x)
不是

GF(2)
上的本原多项式. 另外,可以验证

x+1


GF(24)
的本原元.

2 Matlab 中的有限域计算函数

Matlab 中自带的有限域的计算是在 GF(2m) 上进行的,即在二元域 GF(2) 的扩域中进行计算,其中 1m16 .

由 “1.1 有限域的构造” 的 “例2” 可知,我们只需先找到一个 GF(2) 上的 m 次不可约多项式

g(x)
,得到集合 GF(2)[x]/g(x) ,然后定义其上的加法和乘法分别为模 g(x) 加法和模 g(x) 乘法,即得到有限域 GF(2m) .

然而,这样得到的有限域 GF(2m) 中,元素 x 未必是本原元,这将给后面的(乘法)运算带来很多麻烦. 因此,在不可约多项式

g(x)
的挑选上,我们最好选择一个本原多项式. 这其实就是 Matlab 中的做法.

Matlab 中 GF(2m) 的元素: 在 Matlab 中 GF(2m):=GF(2)[D]/p(D) ,其中 p(D) 为一个 GF(2) 上的 m 次本原多项式.



GF(2m)={am1Dm1+am2Dm2++a1D+a0, | aiGF(2),0im1}



因此,每个

GF(2m)
中的元素
本质上是一个次数小于

m
的多项式,每个元素和多项式之间有“1-1”对应关系. 例如,取



m=3

和本原多项式

p(D)=D3+D+1
,则我们得到有限域

GF(23)
,其中的元素和多项式之间的对应关系如下:

GF(23) GF(2)[D]/p(D) 二进制
0 0 000
1

1
001
2 D 010
3

D+1
011
4 D2 100
5 D2+1 101
6 D2+D 110
7 D2+D+1 111

GF(2) 上的多项式由系数组成的二进制所对应的(十进制)数字来表示. 例如,多项式 p(D)=D3+D+1 的系数组成的二进制为 1011 ,因此,多项式 p(D) 表示为数字 11 .

2.1 定义有限域数组

在 Matlab 中,函数 gf 用来定义一个有限域数组,函数申明如下:

X_GF = GF(X,M,PRIM_POLY)

函数创建有限域 GF(2M) 上的一个数组,使用的 GF(2) 上的 M 次本原多项式为 PRIM_POLYM 是一个 1

16
之间的整数;数组 X 中的元素为 0

2M1
之间的数.

例如,生成有限域 GF(23) 中的所有元素,并令本原多项式为 p(D)=D3+D2+1 .

>> GF8 = gf(0:7,3,13)

GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)

Array elements = 

   0   1   2   3   4   5   6   7

如果不指定本原多项式,则 Matlab 将使用默认本原多项式. 例如

>> gf(0:7,3)

ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements = 

   0   1   2   3   4   5   6   7

在这里例子中,Matlab 使用了 3 次本原多项式

D3+D+1
.

如果不指定次数 M 和本原多项式 PRIM_POLY,则生成二元域 GF(2) 中的元素.

>> gf(0:1)

ans = GF(2) array. 

Array elements = 

   0   1

生成的有限域中的数组可以参与运算(+、、.、.^、\等). 注意:参与运算的操作数必须来自同一个有限域,用于生成有限域的本原多项式也必须相同!

一个典型的例子是计算有限域的乘法表如下:

>> GF8 = gf(0:7,3)

GF8 = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements = 

   0   1   2   3   4   5   6   7

>> GF8'*GF8

ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements = 

   0   0   0   0   0   0   0   0
   0   1   2   3   4   5   6   7
   0   2   4   6   3   1   7   5
   0   3   6   5   7   4   1   2
   0   4   3   7   6   2   5   1
   0   5   1   4   2   7   3   6
   0   6   7   1   5   3   2   4
   0   7   5   2   1   6   4   3

>> GF8 = gf(0:7,3,13)

GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)

Array elements = 

   0   1   2   3   4   5   6   7

>> GF8'*GF8
Warning: Lookup tables not defined for this order 2^3 and
primitive polynomial 13.  Arithmetic still works
correctly but multiplication, exponentiation, and
inversion of elements is faster with lookup tables.
Use gftable to create and save the lookup tables. 
> In gf.gettables at 35
  In gf.mtimes at 20

ans = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)

Array elements = 

   0   0   0   0   0   0   0   0
   0   1   2   3   4   5   6   7
   0   2   4   6   5   7   1   3
   0   3   6   5   1   2   7   4
   0   4   5   1   7   3   2   6
   0   5   7   2   3   6   4   1
   0   6   1   7   2   4   3   5
   0   7   3   4   6   1   5   2

在这里我们用两个不同的本原多项式构造有限域 GF(23) ,得到两张不同的乘法表.

注1:当我们计算 GF(2)[D]/D3+D2+1 的乘法表时,Matlab 给产生一个警告 “Warning: Lookup tables not defined for this order 2^3 and primitive polynomial 13.” 从警告中我们可以看出,Matlab 中有限域的乘法是通过查表来完成的,这样可以显著地提高计算的速度. 我们可以通过命令 gftable 来创建并保存查找表格.
注2:用本原多项式 D3+D+1 D3+D2+1 生成两个不同的元素个数为 8 的有限域,然而这两个有限域是同构的. 一般地,我们有如下有限域同构定理:

定理: 任意两个元素个数相同的有限域一定同构.

与本原元多项式相关的函数

primpoly

函数 primpoly 用于计算

GF(2)
上的本原多项式,函数申明如下:

PR = PRIMPOLY(M, OPT, 'nodisplay')

其中 M 为本原多项式的次数,其取值为 2

16
之间的整数;选项 OPT 的定义如下:

OPT = 'min'  给出一个权值最小的本原多项式
OPT = 'max'  给出一个权值最大的本原多项式
OPT = 'all'  给出所有的本原多项式
OPT = L      给出所有权值为L的本原多项式

字符串 ‘nodisplay’ 用于关闭默认的本原多项式显示方式.

例如,输出 GF(2) 上所有次数为 3 的本原多项式.

>> primpoly(3,'all')

Primitive polynomial(s) = 

D^3+D^1+1
D^3+D^2+1

ans =

11
13

>> primpoly(3,'all','nodisplay')

ans =

11
13

isprimitive

函数 isprimitive 用来检查

GF(2)
上的多项式是否为本原多项式,函数申明如下:

CK = ISPRIMITIVE(A)

其中 A 为一个表示多项式的数字,并且表示的多项式的次数不能超过 16 . 如果 A 为本原多项式,则返回 1 ;否则返回

0
.

例如,检查多项式 D3+D2+1 D3+D2+D+1 是否为本原多项式如下:

>> isprimitive(13)

ans =

 1

>> isprimitive(15)

ans =

 0

其它函数

见 Matlab 帮助.

今天的文章Matlab中的有限域计算分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/4740.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注