有限域
元素个数是素数或素数幂的域
有限域(英文:Finite Field)亦称埃瓦里斯特·伽罗瓦域,其定义为:如果域F仅含有限个元素,则称为有限域,一般记为GF(pn)或Fq(q=pn),它的元素个数是素数p的方幂pn,其中p为其特征,n是它在素域上的次数。
域的概念与数系理论的发展密切相关,最初它是一个进行传统四则运算的简单集合,源于代数方程的求根问题。1771年,法国数学家约瑟夫·拉格朗日(J.L.Lagrange)在讨论三、四次代数方程的各种已知的代数解法过程中,其所谓的“方程系数的有理函数”的集合等价于方程的系数域。至18世纪末,数学家莱昂哈德·欧拉(L.Euler)、高斯(C.F.Gauss)等人,在研究数论等问题过程中所讨论的模素数的剩余类,本质上是一种简单的有限域,但是当时并没有认识到域的抽象概念。19世纪30年代,法国数学家埃瓦里斯特·伽罗瓦(Evariste Galois)第一个给出了域的具体概念,在论文《论数论》中,他使用了域扩张方法构作出全部可能的有限域(伽罗瓦域)。1901年,迪克森(L.E.Dickson)在《线性群及对Galois域的解释》一书中系统总结了前人的工作,把有限域表述成了现代的形式。1931年,范·德·瓦尔登(B.L.Van der Waerden)出版了《近世代数学》一书,使代数学成为了研究抽象代数结构的一门结构数学,书中对于有限域的理论的研究也基本成熟。
有限域具有一些基本性质,如有限域的乘法群是循环群。它的构造方法可分为抽象构造和具体构造,其中,多项式分裂域是一个唯一的个元素的有限域。此外,在现实世界中,有限域具有广泛的应用价值,如计算机科学中,多维信号有限域上的信道编码,可根据相关性来检测(发现)和纠正传输过程中产生的差错。
定义
设是一个有单位元的交换环。如果对中任意非零元,关于乘法有逆元,即存在使,则称为一个域。
有限域
如果域仅含有限个元素,则称为有限域,一般记为。它的元素个数是素数的方幂,其中为其特征,是它在素域上的次数。
简史
早期研究
在人类文化发展的最初阶段,为了计量物体的个数,人们常用手指或其他事物与被计量的物体进行逐一比较,产生了正整数的概念,正整数系是人类建立的第一个数系。经过长久地发展,零、负数、有理数、无理数复数等概念被引入,人们对数系的认识逐渐成熟。
最初的域是可以进行简单四则运算的集合,源于代数方程的求根问题。1771年,法国数学家约瑟夫·拉格朗日(J.L.Lagrange)在讨论三、四次代数方程的各种已知的代数解法过程中,给出了通过原方程根的一个有理函数来求解代数方程根式的核心思想,其所谓的“方程系数的有理函数”的集合等价于方程的系数域。至18世纪末,数学家皮耶·德·费玛(P.de Fermat)、莱昂哈德·欧拉(L.Euler)、高斯(C.F.Gauss)等人在研究数论等问题过程中讨论了一种简单的有限域,即模素数的剩余类的一些性质,实质上已经研究了有限域的性质,但是当时并没有认识到域的抽象概念。
后续发展
19世纪30年代,人们已研究了有理数域、实数域、复数域等抽象概念,法国数学家埃瓦里斯特·伽罗瓦(Evariste Galois)第一个给出了域的具体概念,并在1830年发表的论文《论数论》中,使用域扩张方法构作出全部可能的有限域。但伽罗瓦认为,域的概念在直觉上是清楚的,没有给出域的具体定义。直到1901年,迪克森(L.E.Dickson)在《线性群及对Galois域的解释》一书中系统总结了前人的工作,把有限域表述成了现代的形式。1905年,数学家韦德伯恩(J.H.M.Wedderburn)给出了有限域论中的韦德伯恩定理,揭示了任何有限域都是交换的。1931年,范·德·瓦尔登(B.L.Van der Waerden)出版了《近世代数学》一书,使代数学成为了研究抽象代数结构的一门结构数学,书中对于有限域的理论的研究也基本成熟。
20世纪30年代以来,人们对有限域的研究有了更多的进展。1935年,法国数学家谢瓦莱(C.Chevalley)证明了埃米尔·阿廷(E.Artin,)有关有限域的一个猜想,即谢瓦莱定理:有限域是拟代数闭域。1978年,学者皮埃尔·德利涅(P.Deligne)由于证明了有限域上的广义黎曼猜想,而获得了菲尔兹奖。1985年,美国数学家柯布利兹(NealI Koblitz)和米勒(Victor Saul Miller)各自独立地提出了一个利用有限域上椭圆曲线解的尼尔斯·亨利克·阿贝尔(Abel)群结构性质的公钥密码系统,这就是椭圆曲线加密法。
举例
例1 是存在的最小的有限域,对于加法来说,构成一个交换群,单位元是,的逆元是,的逆元是。对于乘法来说,构成一个交换群,单位元是,的逆元是。
例2 当是素数时,整数集合对于模加法运算和模乘法运算构成一个有限域,记为。换言之,当不是素数时,只能组成一个环,而不是域。
性质
(1)一个有限域有个元素,这里是的特征而是在它的素域上的次数。
(2)一个有限域是它的素域的一个单扩域。
(3)有限域的乘法群是循环群。
(4)设是一个特征为(是素数)的有限域,则的元素个数为,它的加法群是个阶循环群的直和。
(5)韦德伯恩定理:任何有限域都是交换的。
(6)有限域的扩张是一个可分扩张,且是简单的。
(7)有限域是一个完全域。
(8)谢瓦莱定理:有限域是拟代数闭域。
相关概念
子域
定义:若域的一个子集合为,对于的加法与乘法也构成域,则称为的子域,而称为的扩域。
中至少含一个非零元的子集是子域的充分必要条件为:对任意恒有和属于。
域的特征:设是域,如果的单位元的加法阶是无限阶,则称域的特征为;如果的加法阶是素数,则称的特征为(当的加法阶是有限阶时,的阶一定是素数)。在特征为的域中,对于任意都有。
有限域的子域:设是阶有限域,则对的每个正因子,存在且只存在一个阶子域。
素域
定义:不含任何真子域的域称为素域。任何一个域都有单位元,考虑加法群,它有如下两种可能:
(1)对任意非零整数,若,则是的子域且同构于有理数域,此时称的特征(数)为零;
(2)存在正整数,若是使的最小正整数,则必为素数,称为的特征(数)。若,则是的子域且与整数环模的域同构。当时,称是素域,因此任意域都含有一个素子域,它或者与有理数域同构,或者与同构。
与有限域的关系:特征是的素域就是一个有限域。
构造方法
抽象构造
多项式分裂域:该域是与多项式相关的一种域,指域上一个多项式分解为一次因式之积的最小扩域。其定义为:对每个素数和任一正整数,存在一个唯一的个元素的有限域,它就是在上的分裂域。除此之外,无其他个元素的有限域。由于特征为的素域都同构,多项式在同构的域上的分裂域也同构,从而任何阶有限域都同构。
具体构造
元素个数为素数
方法:设有限域的元素个数为某一素数,记为。一般地,当为质数时,的运算,就是运算。即可按一般的实数进行运算,运算结果被除,所得的余数为几,其结果就是几。
举例:构造
以为模数,按照同余的观点,所有整数可分为两类:
(1)类,所有能被整除的整数:类,;
(2)类,所有能被除余的整数:类,。
于是,把作为元素所组成的集合就构成了一个。记,于是在对于模同余的意义下进行四则运算,其结果如下:
加法:;
减法:;
乘法:;
除法:。
元素个数为素数幂
方法:设为质数,为正整数,元素个数为的有限域,记作。构造是比较复杂的。它是通过对进行扩展而实现的。是的次扩展域,是由再加上的次不可约多项式的根构成的。
举例:构造
就是,它是的二次扩展域。的二次不可约多项式为,原根为,阶是。在对于模和同余的意义下,的四个元素为:
,,,。
关于的运算结果如下:
相关理论
弗罗贝尼乌斯自同构
定义:有限域有一个很重要的自同构即弗罗贝尼乌斯自同构。利用特征的域的一条性质,作一个到自身的映射。满足:
因而是一个自同态。其次,是单的。这是因为,所以,即单。因有限,单射必然是满的。所以是的一个自同构,它叫做的弗罗贝尼乌斯自同构。由弗罗贝尼乌斯映射是满射可知,每一个有限域均为完美的。
离散对数
定义:设是有限域,有奇素数,设为生成元,又设是的非零元,定义为“的以为底的离散对数”,它是中唯一满足的一个整数。
定理:设与分别是的非零元与生成元,把看成的元素集合,且假定是奇数,则有同余关系
在密码学中,有限域上的离散对数问题可用于设计公钥密码体制。
原根
定义:域中非元素所构成的乘法群之阶定义为域中该元素的级。若为域中的级元素,则称为次单位原根。若在中,某一元素的级为,则称为本原域元素。
定理:(1)在中,每一个非元素均满足,即都是方程的根。反之,的根必在中。
(2)中必有本原域元素存在。
推论:由中级元素生成的循环群,一定是方程的根。
计算
不可约多项式的个数
多项式的特殊性质:(1)设是中次不可约多项式,,为的一个根,则
(2)设是的某个有限扩域中的元素。若是使成立的最小正整数,则
就是在中的极小多项式
莫比乌斯函数反演公式:设和均是数论函数(即自变量取正整数),如果对每个正整数均有
则对每个正整数均有
其中,求和均是过的所有正因子。
定理:有限域上最高系数为的次不可约多项式的个数为
其中为素数的正整数幂。
多项式因式分解
分圆多项式定义:中彼此不同的级元素为全部根的首一多项式,称为级分圆多项式,记为。
定理:级分圆多项式的次数为。
举例 分解上的多项式
解:共有个根,由定理(1)知,上的所有个非元素都是它的根。的因子有,故在中的非元素的级分别为级。那么可写成如下形式
其中
是以级元素为根;
是以级元素为根;
是以级元素为根;
是以级元素为根;
所以
再引入莫比乌斯反演公式,即可得到上的表示式,则
应用
工程学
混凝土结构受外部环境氯离子侵蚀作用的影响会经常出现钢筋锈蚀和混凝土剥落等耐久性退化问题,早期的混凝土中氯离子的浓度分布的分析方法容易忽视氯离子扩散系数和混凝土表面氯离子浓度的时变性,且所建立的分析模型与实际工程不符。在此基础上,基于有限域的氯离子双时变扩散解析模型,可通过建立氯离子双时扩散控制方程,推导出氯离子扩散场补偿长度的计算公式。该模型还可以合理描述混凝土中氯离子的浓度分布,具有良好的计算精度和适用性。
密码学
有限域上的不可约多项式与本原多项式在密码,编码理论及随机数的产生等方面有着广泛的应用。由于在扩频通信与序列密码中被广泛应用的伪随机序列,可在连续波雷达中用作测距信号、在遥控系统中用作遥控信号、在多址通信中用作地址信号、在数字通信中用作群同步信号等。伪随机序列大部分是利用有限域上的不可约多项式和本原多项式通过反馈移位寄存器和其它非线性逻辑产生的。
计算机科学
在数字通信系统中,信息的传输(或存储)传输过程中的可靠性是避免出现差错的重要问题,信道编码的可根据相关性来检测(发现)和纠正传输过程中产生的差错。为实现面向多维信号有限域上的编码,可应用素元生成的素理想,考虑分圆域代数整数环是主理想,当错误值取自有限域乘群的一个循环子群时,所构造的分圆域中的线性分组码可以纠单个错,为码调制提供了一种代数渐进方法。
参考资料
目录
概述
定义
有限域
简史
早期研究
后续发展
举例
性质
相关概念
子域
素域
构造方法
抽象构造
具体构造
元素个数为素数
元素个数为素数幂
相关理论
弗罗贝尼乌斯自同构
离散对数
原根
计算
不可约多项式的个数
多项式因式分解
应用
工程学
密码学
计算机科学
参考资料