《有限域上的多项式理论.doc》由会员分享,可在线阅读,更多相关《有限域上的多项式理论.doc(41页珍藏版)》请在金锄头文库上搜索。
1、密级:公开 有限域上的多项式理论Polynomial Theory of Finite FieldsI 摘 要域的概念的提出为代数学中的讨论的方便提供了条件,而作为在域中占有重要地位的有限域而言,更是在组合设计、编码理论、密码学、计算机代数和通信系统等领域发挥着自己的作用。多项式理论又是代数学中的基础,它的应用在其它领域也是常见的,本文的主要思想就是将高等代数中建立在数域中的多项式理论进行推广,将有关的性质、定理在有限域上进行验证,进而形成一套建立在有限域上的多项式理论。当下,通信技术已经飞速发展,而保证信息在传输过程中的准确性是通信安全的一个重要前提。本文在第三章给出了有限域上的多项式在该领
2、域的一个具体应用利用本原多项式来进行纠错码的操作。正文部分的结构组成包括:有限域的基本知识、一元多项式、多项式的整除和带余除法、最大公因式、因式分解定理、重因式、多元多项式及本原多项式在纠错码中的应用。本文通过大量理论证明,验证了关于多项式的定理,性质,将数域上的多项式理论建立在有限域上。从结果中可以看出,对于建立在一般数域的多项式理论,大部分的结果在有限域上也是普遍成立的,但是不排除一些特殊的情况。同时,在部分章节的最后也给出了一些只有在有限域中成立,在普通数域中不成立的结论。关键词:有限域;多项式;带余除法;纠错码AbstractWith the concept of the field
3、being raised, it has provided the conditions for the convenience of the discussion in Algebra. Meanwhile, the finite field also plays an important role in combination of design, coding theory, cryptography, commuter and communications systems. Polynomial theory is the basis of Algebra. The main idea
4、 is to put the polynomial theory to the finite field and check the related properties and theorems.Nowadays, the communicational technology has developed rapidly. Keeping accuracy is an important prerequisite for communication security. In the third chapter, this paper introduces the primitive polyn
5、omials applications: Error-correcting code.The text contains: The basis knowledge of finite field, polynomial, divisibility of polynomials, greatest common factor, factorization theorem, repeated divisors, multivariate polynomial and the primitive polynomials applications: Error-correcting code.In t
6、his paper, a number of properties and theorems are checked by theoretical proof. We will establish the polynomial theory of finite field. According to it, we can see that the most parts of the polynomial theory of number field are established in finite field except in some special situations. At the
7、 same time, some conclusions which only established in finite field are given in some chapters. Keywords: finite fields; polynomial; divisibility of polynomials; Error-correcting code I 目 录摘 要IAbstractII第1章 绪论11.1 有限域的发展11.2 有限域的基础理论2第2章 有限域上的多项式52.1 一元多项式52.2 多项式的整除和带余除法92.4 最大公因式142.5 因式分解定理182.6
8、重因式212.7 多元多项式23第3章 有限域上的多项式的应用28第4章 结论34参 考 文 献35致 谢36第1章 绪论1.1 有限域的发展一般地讲,域是可以进行传统算术的四则运算的集合。由此,要定义域首先得有完善的数系,这样逆运算才能进行。历史上,人们把零、分数、负数、无理数、复数引进熟悉经历了漫长的过程。1500年左右,人们已经接受零作为一个数,无理数也用得更随便了。到1700年左右,人们已经很熟悉整数、分数、无理数、负数和复数了,但是对它们还有错误的认识,甚至采取回避的态度。正是因为数系的扩大,才可以进行加法和乘法的逆运算,也就是为代数结构提供了活动的场所,而这一切都是在不知不觉中发生
9、的。从算术开始,人们就知道有理数对加减乘除是封闭的,而且满足交换律、结合律和分配律,也就是我们现在所说的域,但是他们并不知道这就是域的性质。迈向有限域论的第一步发生在古代。这个理论的基本定理是EUCLID原本,用现代语言叙述如下:如果,那么。有限域的另一个重要结果是C. G. Bachet给出的一个算法,如果是自然数且互素,计算非负整数,使得,且,C.G. Bachet的算法允许在有限域中计算逆元。到了19世纪,人们所研究到的域有:有理数域、实数域、复数域和模素数的剩余类域等,然而第一个有具体域的概念,并且构造出一个新的有限域的数学家是年轻的E. Galois,这来源于代数方程的求根问题。18
10、30年,E. Galois发表了一片题为“论数论”的重要论文。他在元域的基础上,采用域扩张的方法构作出全部可能的有限域,结果表面:每个有限域的元素个数必为某个素数的方幂 。而且对某个素数幂,本质上只有一个元有限域。所以后来,为了纪念E. Galois,人们把有限域也叫做 Galois域。有限域的理论最早可以追溯到费尔马(FERMAT 16011665)、欧拉(EULER 17071783) 和高斯 (GAUSS 17771855),他们实质上研究了一种称之为有限素域的有限域。有限域的一般理论则主要是从伽罗瓦(GALOIS 18111832)的工作开始。1830年,他在元有限域的基础上,采用域扩
11、张方法构造出全部可能的有限域,证明了每个有限域的元素个数一定是某个素数的幂,而且对每个素数幂,本质上也只有一个对应的有限域。如今,由于计算机和信息科学的发展,离散的数学结构(对比于连续的数学结构)的研究日益重要、有限域在纠错码、密码学、实验设计、有限群、有限几何等问题中担任重要角色。数域是代数中的一个基本概念。有理数域、实数域和复数域都是我们比较熟悉的数域,这些域有个共同的特点,就是它们的元素个数都是无限的,而有限域最大的特点是只含有有限多个元素。有限域是现代代数学的重要分支之一。有限域作为域,当然具有通常域的一般性质,但又因为它只含有有限多个元素,使得它与我们所熟悉的数域又有很大的不同。有限
12、域具有许多优美的性质,在组合设计、编码理论、密码学、计算机代数和通信系统等许多实际领域有着广泛的应用。特别是最近几十年,随着计算机技术的蓬勃发展,有限域的地位愈加重要。例如有限域的计算和算法分析对计算机代数和符号计算的影响,许多从事应用研究的数学家,开始重视有限域理论的研究和应用,有限域已经成为许多工程技术人员不可缺少的数学工具。另一方面,有限域理论本身也吸引了人们的广泛兴趣,成为许多优秀数学家施展自己才华的场所。数学本身和实际应用领域也不断提出关于有限域的大量数学问题,这些问题的解决或者有益于应用,或者推动数学的发展。有限域上的多项式理论对研究有限域的代数结构,以及对有限域的应用是非常重要的
13、。1.2 有限域的基础理论有限域是域的一种,首先给出一般的域的概念。定义1.1 设是至少包含两个元的集合,在中有一个代数运算,称作加法:这就是说,对中任意两个元,有中唯一一个元与之对应,称为与的和,并记为 (这里的等式表示集合相等,即等号两边的元素相同)。在中还有另一个代数运算叫做乘法,即对中任意两个元,在中都有唯一的一个元与之对应,称为与的积,并记为。如果的这两个运算还满足. 1. 加法交换律 ,。 2. 加法结合律 ,。 3. 中有一个零元满足,。 4. 对中任一元,有中的元,使得,称为的一个负元。. 1. 乘法交换律 ,。 2. 乘法结合律 ,。 3. 中有一个单位元,满足,。 4. 对
14、中任意非零元,有中的元,使得,称为的一个逆元。. 乘法对加法的分配律 , ,。这时我们称为一个域。而所谓的有限域,就是满足上述条件,且元的个数为有限个的一种域。有限域作为一种只含有有限多个元素的域,有着许多其他域所没有的特殊性质,比如说每一个有限域中元素的个数一定是某一素数的幂,而且对任一素数幂,也一定存在相应的有限域;再比如说,任何两个元素个数相同的有限域一定同构,从而可以把它们等同起来,等等。举个有限域的例子。对于非空集合,在的情况下做加法和乘法运算,定义运算规则为:加法:如果,则乘法:如果,则易得,在的情况下是个有限域。实际上,对于素数,集合在普通加法和乘法下,再加上运算,就成为有限域。
15、对于域而言,有一个重要的概念是域的特征。定义1.2 设是一个域。若对任何正整数,都有,就称为特征为的域;若是使的最小的正整数,则称是特征为的域,这时必为素数。数域的特征为0,而的特征为2。若是一个有限域,可证它的特征是某个素数。这只要证明有某个正整数,使。考察,它们都是1的倍数,都属于。因中仅有有限个元,上述倍数中必有两个是相同的。设,且,于是,而是正整数。故以某个素数为特征。对于有限域的元素个数有如下限制:定理1.1 有限域的元素个数必为,其中为素数,。证明 有限域的特征必为素数,于是为的子域。我们把的一个子集叫做生成集,是指中每个元素均可表成 (1-1)其中,本身显然是的一个生成集。在所有的生成集中取其中包含元素最少的一个,仍记为,则中每个元素均可表成(1-1)的形式。现在我们证明对每个,表达式(1-1)是唯一的。因为若又有 则。如果有某个不为零,不妨设,则 (1-2)即可以用表示 (系数仍属于)。由于中每个元素均可用表示,将(1-2)代入表