（应用数学专业论文）有限域上的正规基、最优正规基和对偶基.pdf

四川大学博士学位论文 、 l l blu b 摘要 有限域上的正规基、最优正规基和对偶基 应用数学专业 研究生廖群英指导教师孙琦教授 本文共三章在第一章中，我们给出了有限域上两类最优正规基乘法表的一 个非常有效的算法，并将该算法与其它两种已知算法进行比较，进一步体现了其 优越性 在第二章，我们讨论了有限域上正规基及其对偶基的关系，给出了有限域 f = n 在上一组正规基与其对偶基等价的一个充分必要条件，并由此得到 正舰基或最优正规基为自对偶基的一个等价刻画，还给出了全部自对偶最优正 规基本章还讨论了自对偶正规基的两种推广形式弱自对偶正规基以及其 生成元的某线性组合恰好生成对偶基的正规基，我们给出了这两类正规基与其 对偶基的乘法表和复杂度的一些性质、弱自对偶正规基存在的一个充分必要条 件及其计数 在第三章，我们证明了有限域f 上的原报在范映射j v 的逆映射作用下 ( 2 ( 口) ，p 是的原根) 的分布是均匀的，给出了有限域f 的元是原根的几个 岛 充要条件，并研究了最优正规基的生成元是原根的某些特殊情形 关键词有限域，原根，正规基，对偶基，正规基的乘法表 四j l l 大学博士学位论文 a b s t r a c t n o r m a lb a s e s ，o p t i m a ln o r m a lb a s e sa n dt h e i rd u a l b a s e so v e rf i n i t ef i e l d s m a j o r ：a p p l i e dn u m b e rt h e o r y a u t h o r ：l i a oq u n y i n gs u p e r v i s o r ：s u nq i t h i sp a p e rc o n s i s t so ft h r e ec h a p t e r s i nc h a p t e r1 ，w eh a v eg i v e nt w ov e r yu s e f u l a l g o r i t h m st oc o m p u t em u l t i p l i c a t i o nt a b l e so fo p t i m a ln o r m a lb a s e so v e rf i n i t ef i e l d s t h r o u g hc o m p a r i n g t h e s ea l g o r i t h m sw i t ho t h e rw e l l - k n o w nt w oa l g o r i t h m s w ef o u n d t h a tt h e s ea g o r i t h m sa r ev e r yb e a u t i f u l i nc h a p t e r2 w eh a v ed i s c u s s e dt h er e l a t i o n s h i po fn o r m a lb a s e sa n dt h e i rd u a l n o r m a lb a s e so v e rf i n i t ef i e l d s w en o to n l yg o ts o m es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rw h i c han o r m a lb a s i so ra no p t i m a ln o r m a lb a s i si se q u i v a l e n tt oi t sd u a l n o r m a lb a s i so v e rf i n i t ef i e l d s ，a n do b t m n e da l ls e l f - d u a lo p t i m a ln o r m a lb a s e so v e rf i n i t ef i e l d s ，b u ta l s od i s c u s s e do t h e rt w oe x t e n s i o n so fs e l f - d u a ln o r m a lb a s e sw h i c ha r c w e a k l yn o r m a lb a s e sa n dt h en o r m a lb a s i sw h o s ed u a lb a s i si sg e n e r a t e db yi t sg e n e r a t o r sl i n e a r l yc o m b i n a t i o n s ，a n do b t a i n e ds o m ep r o p e r t i e sf o rt h e i rm u l t i p l i c a t i o n t a b l e sa n dc o m p l e x i t i e s i nc h a p t e r3 ，w ep r o v e dt h a tt h ed i s t r i b u t i o no fp r i m i t i v ee l e m e n t so ff = r n i n 哥岛( ) i su n i f o r m l y ，w h e r e 爿岛( 卢) = q f ：坼( a ) = 序 i st h e i n v e r s e f u n c t i o no f t h en o r m f u n c t i o n n f r i q lo f ao v e r f q w ea l s oo b t a i n e ds e v e r a l s u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rp r i m i t i v ee l e m e n t sa n ds t u d i e ds o m ep a r t i c u l a r c a s e sf o ro p t i m a ln o r m a lb a s e sw h o s eg e n e r a t o ri sap r i m i t i v ee l e m e n to ff k e yw o r d s ： f i n i t ef i e l d s ，p r i m i t i v ee l e m e n t s ，n o r m a lb a s e s ，d u a ln o r m a lb a s e s m u l t i p l i c a t i o nt a b l e s i i 四川大学博士学位论文 刖面 由于在有限域的椭圆曲线密码体制的快速实现当中，通常都采用最优正规 基表示有限域中的元，这就更加促进了对有限域上的正规基，特别是对最优正规 基的研究熟知，关于最优正规基有i 型和u 型两类，有限域中元的乘法的执行 硬件与正规基的复杂度( 即其乘法表丁中的非零元的个数) 有着密切的关系，也 就是说，丁中的非零元越少，有限域的乘法就越简单我们在第一章中给出了有限 域上最优正规基乘法表的一个非常有效的算法，并将该算法与其它两种已知算 法进行了比较，进一步体现了其优越性 在有限域的众多基中，对偶基也是一个非常重要的概念专著 3 】中证明了 有限域上正规基的存在性、对偶基的存在唯一性以及正规基的对偶基仍为正规 基等此外，自对偶基也是一个非常重要的概念c w a n g 给出了自对偶基在有限 域乘法运算中的应用熟知，当n 兰2 时，不存在r 。到r 上的自对偶多项式基 在第二章中，我们给出了任意正规基与其对偶基等价的一个充分必要条件，即以 下的主要结果： 定理2 i 1 ：设f 到疋上的正规基n = a ：悖= 0 ，1 ，n l 的对偶基为 b = 尻l i = 0 ，1 ，r - ，n 一1 ) ，则 1 ) | c 露使b = c n 的充分必要条件是t = t ，其中t 为j v 的乘法表 2 ) _ ) v 为自对偶基的充分必要条件是t = t 。且t r ( a 3 ) = 1 定理2 1 2 ：设为f 到只上的最优正规基，则是自对偶基当且仅当 礼= q = 2 ，且为i 型最优正规基或为i i 型最优正规基 本章还讨论了自对偶正规基的两种推广形式弱自对偶正规基以及其 生成元的某线性组合恰好生成对偶基的正规基我们在本章的第二节和第三节 中分别给出了弱自对偶( 最优) 正规基的复杂度的一些性质、弱自对偶正规基存 在的一个充分必要条件及其计数我们证明了以下主要结果： 定理2 3 3 ：有限域f = e 。在f 口上存在弱自对偶正规基n = f q 矿i i = 0 ，1 ，n l 当且仅当以下三者之一成立： 一i i i 四川大学博士学位论文 ( 1 ) q 为偶数且佗不是4 的倍数； f 2 ) 口与n 均为奇数； ( 3 ) q 为奇数，n 为偶数，r 为奇数，且( 一1 ) 非日中的平方元 其中。旷( r = 1 ，n 一1 ) 生成的对偶基 定理2 3 4 ：有限域f 在日上的弱自对偶正规基的数目等于日上n 级可逆 的拟正交循环矩阵群日( n ，q ) 的阶 日( n ，q ) 1 在本章的最后，我们还给出了生成元的某线性组合恰好生成对偶基的两个 充分必要条件并讨论了这类正规基的乘法表的特点、其乘法表与其对偶基的 乘法表之间的运算关系以及对其乘法表的复杂度，等等 另一方面，椭圆曲线公钥密码体制是被认为当前最有前途的公钥密码体制， 在这一体制中计算有限域日( g 是素数p 的幂) 上椭圆曲线有理点的个数是至关 重要的一步，其经典的s c h o o f 算法被广泛采用该算法的实现需要对很多小素数 p 找到有限域b 。的原根对于b 的原根早就有了系统的研究文献 3 5 】中还有 大量的原根表r o b e r tw f i t z g e r a l d 对有限域上原根的极小多项式进行了研究，并 将其应用到b c h 码中张振祥在【3 8 】中给出了有限域上原根的一个充分必要条 件，最近，霍家佳与张起帆在【3 9 中给出了另一个充分必要条件进而，霍家佳与 张起帆在 3 9 】中还给出了一个算法，利用该算法可以通过b 的原根得到e 。的 原根在第三章的第一节，我们证明了有限域f = f q n 中的原根在i k ( 口) 中的 分布是均匀的，其中卢是k = r 的任意原根，v f k ( a ) 是o l f 在k 上的范函 数在本章的第二节，我们将文 3 8 】和 3 9 的结果加以推广，得到了o f 是f 的原根的几个充分必要条件在第三节中，研究了最优正规基的生成元是原根的 某些情形证明了f = 。在日上的与i 型最优正规基等价的最优正规基，其生 成元为f 的原根的仅有一种，并给出了i i 型最优正规基其生成元为f 2 。的原根 的一个充分条件 i v 四川大学博士学位论文 第一章有限域上最优正规基的乘法表 设q 为素数幂，f = b n 是有限域目的n 次扩域，n = a i i = 0 ，l ，n 1 是f 在上的一组正规基，其中口。= d 口，i = 0 ，1 ，n 一1 对va f 和 v b f ，可设a = ；n - 。1 啦b = 蜀b i c z j7 a i , b j b 显然f 岩曰，故可 记a = ( o 一，o n 一1 ) ，b = ( b o ，一，b 。- 1 ) 设a b = c = ( c o ，c r i 1 ) ，熟知 c f = a q - i t o ( b 4 “) t ，l = 0 ，1 ，n 一1 ，而t o = ( t 粤) 由下式给出： 令o t = o t o ，o t o ：i = n t ：- 0 1t i , j o 。j ，0 isn l ，t i , i 日则称t = ( t ) 为正规基 的乘法表易知，：= t 门，。一j ，t 嚣= 缸1 女o i ，j ，墨n 一1 可见，t o = ( j ) 可由乘法表t = ( 如，j ) 唯一确定，而a b = c 又可由t o = ( 蛾1 0 ) ) 得到显然t 和死中非零元的个数相等，t 中的非零元越少，f 中乘法运算的计算量也就越 小r m u l l i n 等人在 1 】中引入了t = ( t 谢) 的复杂度为丁中非零元的个数， 并证明了c 2 n 一1 当c n = 2 n l 时。称v 为最优正规基， 有许多论文研究有限域的正规基，可参阅专著【2 卅和文献 5 】由于在有限 域的椭圆曲线密码体制的快速实现当中，通常都采用最优正规基表示有限域中 的元，这就更加促进了对有限域的正规基，特别是对最优正规基的研究f 6 - 8 】熟 知，关于最优正规基有i 型和i i 型两类，其构造如下( 证明请参见 1 】) ： i 型最优正规基的构造定理：设n + l 是一个素数，口是模n + 1 的一个原根， 则f 上礼个非单位元的扎5 - 1 次单位根是线性无关的，且组成f 到r 上的一组 最优正规基，记为n = q 旷 i = 0 ，n 一1 ) = a j l j = 1 ，n ，这里o t 是一 个n + 1 次本原单位根，称为f 到f 口上的一组i 型最优正规基。 i i 型最优正规基的构造定理：设2 几+ 1 是一个素数，假设 ( a ) 2 为模2 n + 1 的一个原根 或 女j巧 | | 耐j 砷j 州 | | q 四川大学博士学位论文 ( b ) 2 n + 1 三3 ( r o o d4 ) ，且2 模2 n + 1 的次数为n 则o = r + r - 1 生成一个岛n 到f 2 上的一组最优正规基，这里r 是一个2 n + 1 次本原单位根，记为n = f o ，q 2 ，2 一，= q = r + r - l ，t 2 + r - 2 ，p + r - n ，称为r 。到f 2 上的一组i i 型最优正规基 另一方面，若为f 到r 上的一组最优正规基，vo c ，易知n = n ql 。e n 也是，到品上的一组最优正规基此时我们称正规基与n 等 价高绪洪和h w l e n s t r a 在 9 】中证明了：一个有限域上的最优正舰基与i 型 最优正规基等价或与i i 型最优正规基等价由此立得：f 2 。在如上的最优正规 基只有i 型与i i 型两种g ，a g n e w 等在【6 中指出有限域中元的乘法的执行硬 件与正规基的复杂度有着密切的关系，也就是说。死中的非零元越少，有限域的 乘法就越简单因此计算最优正规基的乘法表t 是快速实现有限域上的椭圆 曲线密码体制重要的环文献【1 0 】中给出了有限域上正规基乘法表的一种算 法，最近孙琦在 1 1 】中改进了【l o 】的算法，并由此给出了特征为2 的有限域上 的i 型最优正规基乘法表的另外一个算法，他证明了下述结果：设只的特征为 2 , n22 ，n = 啦拉= 0 ，l ，尥一l 是f 到e 上的一组i 型最优正规基则 ( a ) 正规基的乘法表t = ( ) = 矿，其中y 是n 阶循环矩阵 e 乜，一，! ，o ，1 ，1 】，u 中的元为t r ( a a 。口，) ，0si ，j 礼一1 ，t r ( c r ) 表示 。、，一 警 f 上元。在e 上的迹函数， ( b ) 如果口= 2 ，对于u 中的元t r ( a o r 。) ，0 i ，j n 一1 ，当i = j 时，有： 丁巾血；) ：o ，若归；一1、“ 【1 ，否则 当i j 、0 i ，jsn i 时，有 n ( 理) = 0 , n 2 * + 2 ，三n ( m 。d n + 1 ) 一2 一 四川大学博士学位论文 本章给出了有限域上最优正规基乘法表的两个非常有效的算法+ 它改进了 文献 1 0 】和孙琦【1 l 】的相应结果对于i 型最优正规基的乘法表，新的算法比文 11 】提出的算法更为有效文【1l 】中未讨论i i 型最优正规基的乘法表的计算方 法，本章对i i 型的情形，也给出了一个有效的算法通过与 1 0 】及 11 给出的算 法的比较，不难看出在椭圆曲线密码体制的应用中，我们给出的算法是非常有效 的至此，关于有限域上最优正规基乘法表的计算就基本清楚了本章的内容主 要取自我们的文章f 1 2 1 1 有限域上最优正规基的乘法表 一王姜结果及兵证明 定理1 1 1 ：设n = o , q h = 0 ，礼一1 ) = 口，。2 ，o “) ( 其中为n + 1 次本原单位根) 为f 到乓上的一组i 型最优正规基，t = ( t i , ，) 为其乘法表，则当 j = 0 ，1 ，n 一1 时，有 t 警，j = 一l ； ( 1 1 1 ) 当i = d ，l ，n l ，且i ；，时，有 = r 喜盏刮4 “m d 如“ ，固 定理1 1 2 ：设n = ，q 2 ，q 2 1 ) = ( = r + r ，1 2 + r ，r n 十r n 为f 2 n 到f 2 上的一组i i 型最优正规基，t = ( t i , j ) 为其乘法表，则 t o , j ：”萎：一； ( 1 1 3 ) 2 1o ，否则 ；3 ) t n - l j ： ：，冀! = n 一1 或2 n 1 三土3 ( m 砌2 n + 1 1 ； ( 1 1 4 ) 2 1o ，否则 ；4 而当i = 1 ，n 一2 时，有 t i , j ： 1 萋三三土( 2 士1 ) ( m o d2 7 2 + ( 1 1 5 ) 一10 ，否则 u 。“圳 不难看出，定理1 1 i 给出的计算方法比文【1 1 】提出的算法简单因为，这里 一3 一 婴型盔堂竖主兰垡笙奎 的算法不需要计算两个n 阶矩阵相乘 定理i 1 1 的证明： 设n = 印f z = 0 ，l ，。- - ，n 一1 ) = ( 皿，舻，一，“ ( 其中。为n + 1 次本 原单位根) 为f 到月上的一组i 型最优正规基令a ：= o 旷，夙：q i + 1 ，0 i n 一1 ，卢2 阮2 血2q 。，眵反= 蒿f 舀岛，我们来证明t = ，) 与p = ( 苴；) 之 间有如下对应关系：对v i ，j = 0 ，i ，n 一1 ，有 屯j = ) ，。( j 其中q 。；s ( 苫) 4 - l ( r o o d 耳+ 1 ) ，且0ss ( # ) ，s ( j ) n 1 。事实上，出n = 2 时，则f 到兄上的i 型最优正规基的对偶 基b 非最优正规基 二、定理及推论的证明 为证明本节的定理和推论，我们需要以下引理： 引理2 1 1 ：设g 为素数幂，f = b n 是有限域日的n 次扩域，f 到上任意 一组正规基n = ( 啦f i = 0 ，1 ，n 一1 ) 的对偶基为b = 屈悼= 0 ，1 ，n 一1 ) 设= o o ，p = 岛，口o