《有限域上一类特殊高斯正规基的复杂度》由会员分享，可在线阅读，更多相关《有限域上一类特殊高斯正规基的复杂度（40页珍藏版）》请在金锄头文库上搜索。
1、四川师范大学学位论文独仓I J 性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师廛碰墓指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容J , I - ，本论文不含 任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印
2、刷 版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检 索：2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录至l J 1 时一类特殊 的b 型高斯正规基复杂度的准确计算公式 h u x i a o l a n 8 6 1 6 3 c o m 第2 页 毕业论文 第一章预备知识弟一早耿亩划识 在本章中，我们主要介绍有限域、正规基及其对偶基以及分圆数的相关概 念、性质和一些基本结果，这些内容为后面研究k 型高斯正规基的复杂度以及 对偶基做好知识
3、储备 1 1 有限域的基本概念和性质 设p 是一个素数，最简单的有限域足p 元有限域，利用初等数论的知识容易构 造p 元有限域进而g = p m ，其中m 足正整数，则g n 元域n 是的n 次扩张，且特 征为p 一 命题1 1 i 1 】设F 是一个域，p 为F 的特征则对于任意的n ，b F ，有 ( a + b ) p “= a p “+ 矿，其中n 是任意正整数 推论1 1 2 设F 口是g 元有限域，则对于每一个Q F q ，均有Q 口= Q 命题1 1 3 【2 】( 有限域的存在唯一性) 对于任意给定的素数p 和正整数佗，均 存在一个口= 矿元有限域与F p 上的多项式妒一z 的
4、分裂域同构 设K = F q ，F = F 口n ，则F 可以看成是K 上的扎维向量空间因此，存在Q f ( ，= l ，2 ，n ) F ，使得 口l ，Q n ) 是F 在上的一组基于是，任取Q F ，有口= a l o f l + + 口n ，其中口l ，a 2 ，a n K 在有限域扩张F 口n B 中，存在许多形式的基众多基中，最重要的有两类： 一类是形如N = 口，Q 叮，Q 口n ) 的正规基；另一类是形如【1 ，p ，胪一1 的多 项式基由于J 下规基形式的特殊性，其应用也最为广泛正规基的优越性质已被 应用于硬件和软件中，从而快速实现大规模的有限域运算【2 5 ，2 6 1 第
5、3 页 第一章预备知识 1 2 有限域上的正规基 关于有限域上的正规基基本知识，可参见专著 3 ，4 】在有限域的椭圆曲线 密码体制的快速实现当中，经常采用最优正规基表示有限域的元所以，对正规 基，特别是最优正规基的研究尤其重要1 9 8 8 年，M u l l i n 等【5 】引入了n n 在F 口上 的正规基的乘法表T = ( t i d ) n n ，T 中非零元的个数称为的复杂度，记为， 证明了2 n 一1 当= 2 n 一1 时，称为最优正规基G A g n e w 6 指出有 限域中正规基复杂度越小，即乘法表中非零元个数越少，则乘法运算越简单因 此，计算最优正规基的复杂度是快速实
6、现有限域上的椭圆曲线密码体制重要内 容 1 9 9 2 年，高绪洪等f 2 2 1 证明了有限域上的最优正规基或与I 型最优正规基等 价或与I I 型最优正规基等价，所以最优正规基只有I 型和I I 型两种，其构造定 理如下： 定理1 2 I 7 1 设n + 1 是一个素数，a M 模n + 1 的一个原根，这里q 是一个 素数方幂则F 口。中n 个非单位元的n + 1 次单位根在n 上是线性无关的，且构 成F 驴在n 上的一组最优正规基 定理1 2 1 给出的最优正规基叫做I 型最优正规基 定理1 2 2 1 7 设2 n + 1 是一个素数，假设 ( 1 ) 2 为模2 n + l 的一
7、个原根； 或 ( 2 ) 2 n + 1 兰3 ( r o o d4 ) ，且2 为模2 n + 1 的次数为n 则Q = ，+ r - 1 生成F 2 。在F 2 上的一组最优正规基，这里r 是一个2 n + 1 次本原单位 根 定理1 2 2 给出的最优正规基叫做I I 型最优正规基 1 9 9 0 年，A W a s s e r m a n n 把最优正规基推广到更一般的b 型高斯正规基【8 】， 其构造定理如下： h u x i a o l a n 8 6 1 6 3 c o r n 第4 页 毕业论文 第一章预备知识 定理1 2 3 8 】设g 是素郯的方幂，礼和七是正整数，满足h
8、+ 1 为素数， 1 t ( k n + 1 ，p ) = 1 ，p 七n 是梳+ 1 次本原单位根，s 是g 模尼n + 1 的阶，且( 譬，n ) = 1 设9 是z ；n + 1 中的尼阶元，A = 9 。Io t k 一1 ) ，A = q i f E 4 ) ( o i 佗一1 ) 则A o = A ，且 O t ：F 矿2 A 生成F q n 在F q 上的一组正规基= O t i = Q 叮t l i = 0 ，l ，n 一1 ，称为F g 。在 峨上的忌一型高斯正规基，其复杂度吼满足： “) 俨乜p 讹 Ik n 一1 ，p 限 由定理1 2 1 1 2 3 可知，1 一型高斯
9、正规基即为I 型最优正规基，g = 2 时 的2 - 型高斯J 下规基即为I I 型最优正规基 1 3 有限域上基的对偶基 ， 定义1 3 1 1 1 0 】设有限域F = n 为有限域K = F q 的扩域，我们定义 正F K ：FH K 霉F K ( Q ) = Q + Q 口- 4 - Q 口2 - 4 - + Q 口r - ， 为F 到K 上的迹映射 在有限域的众多基中，对偶基也是一个非常重要的概念，利用迹映射可以引 入对偶基的概念 定义1 3 2 1 1 0 】有限域在F q 上任意两组基i j i = Q 1 ，嘞，O r n 和万： l ，阮，风) ，若 嘶矧： 1 江五 10
10、，i J h u x i a o l a n 8 6 1 6 3 c o r n 第5 页 毕业论文 第一章预备知识 则称万为西的对偶基，其中n 为F q 。到F q 上的迹映射特别地，当万= 瓦时，称石为 自对偶基 利用线性变换的知识，可以证明以下结果： 定理1 3 3 1 1 1 】有限域砸口n 在F 叮上任意基均存在唯一的对偶基，且正规基的 对偶基仍为正规基 自对偶基和正规基( 特别足自对偶正规基) 在有限域中起着非常重要的作用 例如，在指数的计算，有限域基的乘法表计算以及在密码公钥体制，编码理论中 均有广泛运用所以，自对偶( 正规基) 的研究在有限域理论中尤其重要，对于自 对偶正规基，
11、L e m p e l 和S e r o u s s i 1 2 i Kg ) 了如下结果： 命题1 3 4 1 1 2 】有限域F q n 在上存在自对偶正规基当且仅当口为偶数 i n 不是4 的倍数或g 与n 均为奇数 命题1 3 5 1 1 6 】( 1 ) 虬n 在F 口上的I 型最优正规基为自对偶正规基当且仅 当n = q = 2 ( 2 ) I I 型最优正规基为自对偶正规基 命题1 3 6 1 1 3 】设是F 口n 在F 口上的I 型最优正规基，M 为其对偶基， C M 为M 的复杂度则 一 J3 n 一3 ，g 为偶数， I3 n 一2 ，口为奇数 命题1 3 7 1 1 4
12、 】设= O r ，Q 口，Q 矿- 1 ) 是F 口n 在F q 上的2 - 型高斯正规基 则= Q ，Q 口，Q q “- 1 ) = 口= r + r 一1 ，印= r 2 + r 一2 ，扩= r n + r - n ) ， r 殇n l - I 为2 n + 1 次本原单位根，且 ( 1 ) T r ( a ) = - 1 ，其中n ( Q ) = 印。为Q F q n 在F 口上的迹映射 h u x i a o l a n 8 6 1 6 3 c o r n第6 页毕业论文 第一章预备知识 ( 2 ) N 的复杂度瓯满足 ： 2 俨1 胪2 ， 【3 n 一2 ，P 2 - 命题1
13、 3 8 1 1 4 】设g 是素数p 的方幂，N = Q ，印，Q 矿以是F g n 在F 口上 的2 - 型高斯正规基，B = p ，伊，矿1 ) 为的对偶基则 ( 1 ) p = 丽O 一2 ，o ( 2 ) 当p = 2 时，为自对偶正规基，从而g = 2 ；当p 为奇数时，B 的复杂 度G 日= 4 n 一4 命题1 3 9 1 1 7 设= _ 【O t ，o e q ，o l q ”1 t F q 。在上的肛型高斯正规基， B = p ，伊，矿1 ) 为的对偶基则 曼k n + l k - = 0 1 。( m o d2 ) , 其中p 为F 口的特征，由表示匙他+ l 在乘法群
14、嵫中的逆元 1 4 分圆数的基本性质 定义1 4 1 设P 和r = k n + 1 为素数，且( r ，P ) = 1 ，月为模r 的单位群Z ；中 的k 阶子群，p 既一。是r 次本原单位根令 a i = ：伊， = 0 ，l ，n 一1 ， 口A 以及A i = g i l A ) z ；( o i n 一1 ) 则元素伽，Q l ，Q n l 叫做F g n 在F 口上的k 阶高斯周期，且定义分圆数为： m 巧= I ( 1 + A ) n I ( o t ，歹几一1 ) 注记l 由分圆数m 巧的定义知：m i j 1 ，当且仅当存在z ，y 月，使得 l + x ，l + y A j
15、 换句话说，存在z ，可7 臻n + 1 - - 一1 ) ，使得z Y ，昙A ，而l + z A 命题1 4 2 1 2 1 】若n 2 为正整数，r = k n + 1 为奇素数，是z ：n + l 中的七阶 h u x i a o l a n 8 6 1 6 3 c o r n 第7 页毕业论文 第一章预备知识 兀，其中A = 则 ( 1 ) 仃o J + J l = m n - j ，J l ，0 是F 口n 在峨上的k - 型高斯正规基 ( 2 ) 若s 是q 模r = k n + 1 的阶，则( 譬，几) = 1 ( 3 ) Z ；中陪集A = A o ，A 1 ，A n 一1 两两无交，且缉= 设= 啦= Q 叮tH = 0 ，1 ，n 一1 ) 是K n 在F g 上的一组高斯正规基， m 巧和A t 满足命题1 4 2 中的条件，并设如 3 瓯= 4 n - 7 , p = 2 , 耻 6 n - 2 1 , p = 2 , 班 ：f L 6
