（应用数学专业论文）利用代数曲线构造序列和码.pdf

研究生签名：! 冱日期：主竺丝：垒：1 2 3 东南大学学位论文使用授权声明 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印，缩印或其他复制手段保存论文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 _ 蛘 研究生签名： 过2 主 导师签名： 日期幽够，2 ，) 日期：塑! ：兰：7 数 造 密 这 两个问题吸引了很多人的关注本文主要利用有限域上平面代数曲线的算术理论( 代数函 数域理论) 来研究这两个热点问题 在流密码体系中，密钥流序列是元素取自有限域的伪随机序列为了抵抗b e r l e k 锄p - m a s s e y 算法攻击，首先需要构造具有高线性复杂度的密钥流序列同时基于对密码稳定 性的考量，还需要构造具有高错误线性复杂度的密钥流序列 对于非周期序列的情形，x i n g - l 锄利用函数在有理位的局部展开给出了单个非周期 序列的构造，本文给出了x i n 乎l a m 构造的单个非周期序列的错误线性复杂度的一个下界， 并把n g 利用函数局部展开得到多重序列的构造推广到更一般的情形对这样得到的多 重序列，本文同样给出了其联合错误线性复杂度的一个下界 对于周期序列的情形，将) ( i n g - d i n 乎k 啪a r 关于单个序列的构造推广到多重序列的 情形，并证明这样得到的多重序列其联合线性复杂度及错误联合线性复杂度都可以很高 此外，基于函数域的自同构群的结构，利用函数域上函数在高次位的赋值及在有理位的赋 值，给出多重周期序列的两种新的构造方法分析并证明了当函数满足一定的条件时，这 样得到的多重周期序列的联合线性复杂度和错误联合线性复杂度可以达到最大值，即等 于周期特别地，利用h e m i t i a n 函数域的相关性质，构造出三类多重周期序列证明了当 错误个数小于重数减2 时，其错误联合线性复杂度可达到多重序列的周期 在纠错码码字个数的渐近界方面本文考虑两类特殊的码：常重复合码和二元自正 交码对于常重复合码，本文利用剩余多项式环给出常重复合码的一个构造当固定最 小距离d 和码长n 时，此构造给出了的常重复合码最大码字个数a 。( n ，d ，p o ，一1 】) 的 一个下界当最小距离d = 3 时，这个下界改进了l u o 等给出的一个下界而当最小距 1 邢朝平，新加坡南洋理工大学数学系教授，是作者在新加坡南洋理工大学联合培养时的导师 1 离d 4 时，据我们所知，目前还没有其他关于a 。( n ，d ，【岫，一l 】) 的下界特别地，当 最小距离d = 5 ，我们构造的常重复合码的码字个数和最优的码字个数达到同一个数量级 对于二元自正交码，本文证明了该码是渐近达到g i l b e r t 、协s h 锄o v 界的此外，我们 给出了二元自正交码的两类构造：一类是利用达到t s f a s m a n - 甜u t z i n k 界的代数几何 码和一些性质良好的二元正交码的链接码：另一类是借助达到t s f a s m a n 甜u t z i n k 界 的代数几何码在自对偶基给定的映射下的像通过这两种构造给出了信息率r 和相对最 小距离6 之间的关系当信息率r = 1 2 时，可以得到一簇相对最小距离6 0 0 5 9 5 的二元 自正交码，此时构造得到的码很接近g i l b e r t 一、k s h 锄0 v 界 本文还研究了周期序列和循环码、多重周期序列和1 生成拟循环码之间的对应关系， 利用这种对应关系给出周期序列和多重周期序列的复杂度分布，部分回答n i e d e r r e i t e r 的 一个公开问题此外，利用代数函数域的自同构在有理位集合上的作用给出了拟循环码的 构造特别地，在h e r i n i t i a n 函数域上得到了三类拟循环码，并且这样得到的拟循环码具 有良好的编码译码算法 2 e sf r o ma l g e b r a i ce st r o ma l g eb r a l c c a n d i d a t ef b rp h d ：d i n gy a n g s u p e i s o r ：p r o 恼s o rc h e nj i a n 1 0 n g ，p r o 砖s o r n gc h 瓣p i n g 2 d e p a r t m e n to fm a t h e m a t i c s ，s o u t h e a s tu n i v e r s i t 弘n a n j i n g ，p r c h i n a k e ”r d s ：s e q u e n c e s ，l i n e a rc o m p l e ) 【i t y e r r o rh n e a rc o m p l 嘲t y ，c o n s t a n t c o m p o s i t i o n c o d e s ，s e m o r t h o g o n a lc o d e s ，q u a s i c y c l i cc o d e s ，以g e b r a j cc 删，a l g e b r a i cg e o m e t 巧c o d e s a b s t r a c t ：s i n c eg o p p ad i s c o v e r e dt h a tt h ea l g e b r a i cc l l r v e so v e rf i n i t ef i e l d sh a v e 砒e r e s t i n g 印p l i c a t i o ni nc o d i n gt h e o 以i e ，c o n s t r u c t i o no fa l g e b r a i cg e o m e t 珂c o d e s ， m a i l yc o d i n ga n dc 巧p t o g r a p h ye ) 【p e r t st 巧t od of u r t h e rr e s e a l r c h e so nc o d i n ga n dc r y l ) - t o g r a p h yb ya d o p t i n gt h ea l g e b r a i cc u r v e s i nr e c e n ty e a r s ，t w 0p r o b l e 瑚i nc 哪t o g r a p h y a n d c o d i n g ，i e ，c o 璐t r u c t i n ga n da n a l y z et h el i n e 盯c o m p l e ) d t yo fk e y s t r e a mi ns t r e a mc i _ p h e ra n dt h ea s y m p t o t i cb o u n d0 ft h em a x i m a ls i z eo fe r r o r - c o r r e c t i n gc o d e s ，r e s p e c t i v e l y h a v l eb e e na t t r a c t e dm o r ea n dm o r ea t t e n t i o i l s b ye m p l o 妒n gt h ea r i t h m e t i ct h e o 珂o f p l a n ea l g e b r a i cc u r v e so v e rf i n i t ef i e l d ( t h e o uo fa l g e b r 缸cf u n c t i o n 矗e l d ) ，t h er e s e a r c hi n t l l i st h e s i sm a j n l yd e a l s 丽t ht h e s et w o i m p o r t a n tp r o b l e i l l s i ns t r e 锄c i p h e rs y s t e m ，k e y s t r e a mi saq u a s i r a n d o ms e q u e n c eo fe l e m e n t so fa n i t e f i e l d i no r d e rt or e s i s tt h eb e r l e k a m p m a s s e ya l g o r i t h ma t t a c k ，t h ek e y s t r e a mm u s th a v e l l i 曲h n e a rc o m p l e 五t y b a s e do nt h er e q u i r e m e n to fs t a b i l i t yo ft h es t r e a mc i p h e rs y s t e m ， t h ek e y s t r e 锄a l s ds h o u l dh a v eh i 曲e r r o rl i n e a rc o m p l e x i t y f l o rn o n - p e r i o d i cs e q u e n c e sc a s e ，b yu s i n gt h el o c a ie x p a 瑚i o no faf u n c t i o na ts o m e r a t i o n a l lp l a c e ，n 分l a mp r o p o s eac o n s t r u c t i o nf o rs i n d es e q u e n c e s i nt h i sd i s s e r t a t i o n ， a 】o w e rb o u n do fe n o r1 i n e a rc o m p l e ) d t yf o rx i n 乎l a mc 0 i l s t m c t i o ni s 舀v e n m o r e o v e r ，t h e c o 璐t r u c t i o no fx i n g ，w 址c h 舀、髑m u l t i s e q u e n c e sb yt h el o c a le x p a n s i o no fa f u n c t i o n ，i s g e n e r a l i z e d f | u r t h e r m o r e ，al 陀rb o u n d0 fj o i n te r r o rl i n e a rc o m p l e ) d t yf d ro u ro b t a j n e d n m l t i s e q u e n c e si j s 百v e ni nt h es a m ew a 弘 e ；ys t u d 蛐唱t h ec o n s t m c t i o n s0 fp e r i o d i cm u l t i s e q u e n c e s ，t h ec 0 1 l s t r u c t i o no f ) ( i n g _ d i n 分k u m a rw a sg e n e r a h z e dt om u l t i - c a s e f i u r t h e 咖o r e ，t h ej o i n tl i n e 缸c o m p l e x i t ya n d 2 p r o x i n gi s 研t ht h ed i 、秘i o no fm a t h e m a t i c a ls c i e n c ，s c h c l o lo fp b y s i c 甜a n dm a t h e m a t i c 甜 s c i e n c e s ，n a n y a n gt e 妇n o l o 百c a lu 1 1 i v e r s i t y s i n g a p o r e h ei st h es u p e r 嘶ro ft h ea u t h o rd u d n gh e r s t u d yi ns i n g a p o r e 3 m o r e o v e r ，t oo b t a i nt h ec o n s t m c t i v eb o u n do ni n f 6 m a t i o nr a t era n dr e l a t i v e l i n i m 呦 d i s t a n c e6 ，陀u s et w od i 艉r e n tw a 沪t oc o n s t r u c tb i n a r ys e 璩o r t h o g o n a l lc o d e s i nt h ef i r 8 t c o 璐t r u c t i o n ，t h ed e s i r e dc o d e sa r eo b t a i n e db yc o n c a t e n a t i n ga l g e b r a i cg e o m e t 可c o d e s w h i c ha c h i e v e st h et s m a i 卜矾u t z i i l l 【b o u n d 耐t hb i n a u s e 搀o r t h o g o n a lc o d e s i nt h e s e c o n dc o n s t r u c t i o n ，陀出og e tt h ed e s i r e dc o d e sb yc o l l s i d e r i n gs e 睢o r t h o g o n 砒a l g e b r a i c g e o m e t ua n de x p r e s st h e s ea l g e b r a i cg e o m e t r yc o d e si n t ob i n a r ys e 推o r t h o g o n a lc o d e s b ye m p l o y i n gt h es e l f - d u a lb a s i s i np a r t i c u l a r ，w eg e t6 0 0 5 9 5w h e nr = 1 2 t h i s s h o w st h a to u rc o i l s t r u c t i v ec o d e sc a na p p r o a c ht og i l b e r t v 打s h 锄o vb o 皿d t h ec o r r e s p o n d e n c e 8b e t r e = e np e r i o d i cs e q u e n c e sa n dc y c l i cc o d e s ，p e r i o d i cm u l t i s e - q u e n c e sa n do n e g e n e r a t e dq u a s i c y c l i cc o d e sa r ea k oe ) c p l o r e d b yu s i n gt h i sc o r r e s p o n - d e n c e ，t h ed i s t r i b u t i o no fs e q u e n c e sw i t h 政e dl i n e a rc o m p l e 茹t ya n dt h ed i s t r i b u t j o no f m u l t i s e ( 1 u e n c e s 而t hf i x e dj o i n tl i n e a rc o m p l e ) 【i t ya r e 舀v e n ，w h e r et h es e c o n dd i s t r i b u - t i o n 舀v e sap 盯t i a la 璐w e ro fa no p e nq u e s t i o np r o p o s e db yn i e d e r r e i t e r f u r t h e 咖o r e ，b y 4 5 i o n a lp l a c e ，ac o n - s p e c i a l lp r o p e r t i e s e 伍c i e n te n c o d i n g 第一章 1 1 1 2 1 3 第二章 2 1 2 2 2 3 目录 绪论1 研究背景1 本文的研究结构和主要结论4 符号说明7 非周期序列8 单个非周期序列8 2 1 1 利用函数域构造几乎完全序列8 2 1 2 七错线性复杂度1 1 仇重非周期序列1 4 2 2 1 利用函数域构造几乎完全多重序列1 4 2 2 2 七错线性复杂度1 7 本章小结1 9 第三章周期序列 2 0 3 1 单个序列的迹函数构造2 0 3 1 1 单个序列的构造。2 0 3 1 2 椭圆函数域上的序列2 2 3 2 多重序列的迹函数构造2 3 3 2 1 一般函数域2 3 3 2 2 椭圆函数域2 6 3 3 多重序列的新的构造2 9 3 3 1 利用高阶位构造多重序列2 9 3 3 2 利用有理位构造多重序列3 2 3 4h e 咖i t i a n 函数域上的序列3 5 3 4 1 周期为( q 2 1 ) 的( g 1 ) 重序列3 6 3 4 2 周期为p 的口3 肋一1 重序列3 9 3 4 3 周期为( q 2 一g + 1 ) 的口重序列4 0 3 5 本章小结4 2 第四章常重复合码 4 3 4 1 射影直线4 3 6 4 4 4 7 5 0 第五章自正交码5 1 5 1 代数曲线和代数几何码5 1 5 2 二元自正交码5 2 5 2 1 利用接连码构造二元自正交码5 3 5 2 2 利用自对偶基构造二元自正交码5 4 5 3 二元自正交码的渐近界5 6 5 4 本章小结5 8 第六章周期序列和码5 9 6 1 单个周期序列和循环码5 9 6 2 多重周期序列与1 一生成拟循环码6 2 6 3 构造拟循环码6 6 6 3 1 指数为g ，码长为9 3 一g 的拟循环码6 8 6 3 2 指数为9 3 加，码长为9 3 的拟循环码6 9 6 3 3 指数为g + 1 ，码长为q 3 + 1 的拟循环码6 9 6 4 本章小结7 0 参考文献 7 1 附录一攻博期间完成论文列表 附录二个人简历 附录三致谢 7 7 8 7 9 8 0 代数数论和代数几何的角度研究有限域上的代数曲线及其对应的代数函数域产生了一门 新的学科一算术代数几何在很长的时间内，对有限域上代数曲线及其代数函数域的研究 只是纯数学的方面直到上个世纪8 0 年代末，g o p p a 发表了三篇重要论文【2 5 ，2 6 ，2 7 1 ，他 发现了有限域上代数曲线，特别是有很多有理点的曲线在编码上的应用，即代数几何码 的构造这个有意义的发现吸引很多编码密码学者从代数函数域的角度去研究编码和密 码1 9 8 5 年提出的椭圆曲线密码体系就是一个很好的应用例子最近十年，有限域上的 代数曲线及其函数域自身也有很多有意义的结果，如构造具有多个有理点的代数曲线，改 进了渐近点数的界同时有限域上代数函数域也有了更广泛的应用，在构造低差异序列、 拟m o n t ec a r l e 方法、构造h a s h 函数、构造几乎完全序列等方面都得到了好的结果( 见【7 3 1 ) 本文主要利用有限域上平面代数曲线的算术理论( 代数函数域理论) 研究通信中的两 个重要的热点问题：流密码体制中密钥流序列的线性复杂度和纠错码码字个数的渐近界 在流密码体系中，明文和密文都是元素取自有限域的字符串，通过和一个密钥流序列 的运算进行加密和解密实际中使用的序列都是具有预先可确定性的和可重复性的伪随 机序列，可由初始状态及某种递归关系确定产生工程中使用的序列大多是利用线性反馈 移位寄存器产生的，即由初始位置及给定的线性关系唯一确定的序列生成序列的最短线 性移位寄存器的长度称为序列的线性复杂度为了抵抗b e r l e k a m p m a s s e y 算法攻击，需要 具有高线性复杂度的密钥流序列因而序列的构造以及随机序列的线性复杂度分析成为 密码领域研究的一个热点对于单个序列，人们通过代数函数域的性质，给出了若干非周 期序列和周期序列的构造，并给出其线性复杂度的值近年来，d a w s o n 和s i m p s o n 1 1 】以 及h a w k e s 和r o s e 【3 1 等提出基于w o r d 的流密码体系( 向量流密码体系) ，引起了人们对多 重序列及其联合线性复杂度的关注上个世纪9 0 年代，基于对密码稳定性的考量，人们希 望密钥流序列具有更好的稳定性，即改变密钥流序列若干位不会导致密钥流序列线性复 杂度明显的降低为此，s t 锄p 【7 9 和d i n g 1 2 】分别提出了错误线性复杂度和球面线性复 杂度的概念对于多重序列的情形，m e i d l 和n i e d e r r e i t e r 6 1 1 推广了s t 锄p 【7 9 】错误线性 1 2东南大学博士学位论文 复杂度的定义，给出了多重序列的三种错误线性复杂度的刻画 在引入线性复杂度、联合线性复杂度和错误线性复杂度后，人们对线性复杂度进行 了深入的研究，主要有以下几个方面： 1 研究流密码体系中使用的特殊序列的线性复杂度在现有的流密码体系中，大多采 用一些特殊的序列作为密钥流序列，为了确保流密码可以抵抗b e r l e l c a m p m a s s e y 算 法攻击，人们需要对这些特殊的序列进行详细的复杂度分析h e l l e s e t h 【3 2 】等研究 了l e m p e l c o h e a s t m a n ) 【1 】l i e 序列，s h p 盯1 i n s h 【7 8 】研究了n a o r - r 电i n g o l d 函数对应的 线性复杂度，g a r a e v 等 2 3 】和h e u e s e t h 等 3 4 】研究了s l i d e l i l i k o v 序列的线性复杂度 2 对单个序列和多重序列的统计性质的研究n i e d e r r e i t e r 、m e i d l 和w 抽g 等做了很多 关于序列线性复杂度的期望和方差的工作，详见 8 8 】，【6 8 】，【5 6 】，【5 8 】，【2 2 】n i e d e r 降 i t e r 在f 6 7 】中提出了公开问题2 ：给定序列长度n 和错误个数后的渐近关系，能否给出f 口上 任意序列s 的n 次忌错线性复杂度l 础( s ) 的刻画n i e d e r r e i t e r 在 6 7 】中还提出了公开问 题4 ：对满足扎2 己佗的l ，决定f 。上联合线性复杂度为l 的佗周期m 重序列的个 数心，m ( 己) 3 具体构造具有好的线性复杂度的( 多重) 序列n i e d e r r e i t e r 等利用有限域上离散傅里 叶变换等工具对某些特殊周期证明了具有高( 错误) 线性复杂度的周期序列的存在性， 见【6 6 】，【7 1 】，【6 0 】关于利用函数域构造序列，可追溯到1 9 8 6 年，k 如l 【i 【4 0 】首次利 用椭圆函数域构造拟随机周期序列这里构造序列的随机性是基于椭圆曲线上的离 散对数问题随后，g o n g 和b e r s o n 等人 2 9 】利用超奇异椭圆曲线给出了一类二元伪随 机周期序列1 9 9 9 年，x i n g 等 9 8 】利用函数在有理位处的局部展开首次给出一类几乎 完全的非周期序列的构造2 0 0 3 年，x i n g 、d i n g 和k u m a r 【9 7 利用代数函数域构造了 一系列具有高线性复杂度低相关度的周期序列特别地，当函数域为椭圆函数域时， h u 等f 3 5 】利用k o h e l 和s h p a r l i n s l d 【4 2 】给出的有限域上椭圆曲线指数和的一个上界改 进了) ( i n gf 9 7 1 等的结论 4 线性复杂度的算法k a l i d a 在【3 9 】，l a u d e r 和p a t e r s o n 在【4 4 】，s t a m p 和m a r t i n 在 7 9 】以 及) ( i a 0 和w e i 在9 1 1 中给出了错误线性复杂度的有效算法n i e d e m t e r 在【6 7 】中提出了 公开问题3 ：设计能有效计算七错线性复杂度的的算法 5 线性复杂度与错误线性复杂度的关系在七一错线性复杂度概念提出后，d i n g 等曾猜想 在线性复杂度和七错线性复杂度之间会有一个权衡，互相制约但n i e d e r r e i t e r 在【6 6 】中 研究了一类周期序列具有好的线性复杂度同时也具有好的一错线性复杂度，否定了这 个猜想n i e d e r r e i t e r 和s h p a r u n s k i 在【7 0 中证明了存在无穷多个线性复杂度为的一 周期序列，使得当错误个数七很大时，其惫一错线性复杂度为一1 k u r o s a w a 等在 4 3 】中 第一章绪论 研究了对于周期序列s ，使得线性复杂度发生变化的最小错误个数k a i d a 在【3 9 】中 给出了满足l ，七( s ) 0 ，考虑，在尸处的局部展开，有 o o ，= 口n 矿，口n f 口 ，l = o 由此可得无穷序列 a 2 ( ，) = ( n 0 ，口1 ，n 2 ，) ； 并有 命题2 1 5 9 9 】若d d e g ( ( 厂) ) 且i = 印( ，) o ，则上述序列a 2 ( ，) 是( d + 一1 ) 一完全 的，即l n ( a 1 ( 厂) ) 苎专业对任意n 1 1 ) 完 ) 一完 注2 1 - 8 类似于命题2 1 2 ，我们有： 若d d e g ( ( ，) o o ) 且即( ，) o ，则序列b 2 ( ，) 改变前m 个位置后得到的序列s 是 + 2 m + + 1 ) 完全的更进一步，若除子m ( ) ( + 1 ，) ，则s 仍是( d + z ，+ 1 ) 一完全 的 2 1 1 3 第三类序列 若即( ，) o 设= 印( ，) o ，考虑厂在p 处的局部展开，有 ，= 幻”以+ 口n 矿，如，f g j = 1 n = 0 由此可得无穷序列 a 3 ( ，) = ( 口1 ，n 2 ，口3 ，) ； 并有 命题2 1 9 【9 9 】若d d e g ( ( ，) ) 且= 即( ，) o ，则上述序列a 3 ( ，) 是d 一完全的 注2 1 1 0 类似于命题2 1 2 ，我们有： 若d d e g ( ( ，) ) 且即( ，) 0 ，则序列a 3 ( ，) 改变前m 个位置后得到的序列s 是 + 2 m ) - 完全的更进一步，若除子m ( ) o 。( 厂) ，则s 仍是( d ) 一完全的 【9 9 】中给出了特征为2 的域上出完全序列的一种具体构造方法 命 若 则 例 由 为 由 2 1 2 尼错线性复杂度 本节将证明在上节利用代数函数域上局部展开构造的单个序列具有好的七错线性复 杂度本节引入如下记号： f f q f q 上的代数函数域； p f 上一有理位： p 的素元且满足d e g ( t ) = 2 ； ，- 印( ，) o ；，f f q ( ) 先考虑1 错线性复杂度，有 命题2 1 1 3 设，f l ( t ) ，d d e g ( ( ，) o 。) 且印( ，) o 设a 1 ( 厂) = ( 口1 ，盘2 ，n 3 ，) 是由 第一种构造方法得到的d 一完全序列则序列a 1 ( ，) 的1 错线性复杂度满足对任意几1 有， 圳a 。( 川半 证明：记s n 为截取无穷序列s 前n 项得到的f 口上长为礼的序列设n 为任意正整数，入为 o ，1 】中 一有理数设s 为由a 1 ( ，) 在前礼项中更改一位后得到的无穷序列分情况讨论： 即 1 1 有 己n 。1 ( a 1 ( ，) ) m j n ( a n + l d ) 2 ，( 扎+ 1 一d 一2 入礼) 2 ) ， 当入= 1 3 时，上式右边的两个值相等，从而取得最大值，即 l ，l ，1 ( a 1 ( ，) ) ( n + 3 3 d ) 6 结论得证 口 现在我们对于一般的七，考虑上述d 完全序列a 1 ( ，) = ( 口1 ，n 2 ，口3 ，) 的七一错线性复杂 度，则有 命题2 1 1 4 设，f f 口( t ) ，d d e g ( ( ，) o 。) 且即( ，) 0 设a 1 ( ，) = ( 口1 ，口2 ，n 3 ，) 是由 第一种构造方法得到的d 完全序列则序列a 1 ( ，) 的七错线性复杂度满足对任意n 1 有， 划“，) ) 型篱筹孚型 证明：记s n 为截取无穷序列s 前礼项得到的f 。上长为扎的序列设n 为任意正整数，a 为【o ，1 】中 一有理数设s 为由a 。( ，) 在前几项中更改七位后得到的无穷序列我们利用归纳法证明， 忌= 1 时，由命题2 1 1 3 得证设结论对 艮的情形成立现在考虑南的情形，我们分情况 讨论： 首先，若这后个错误全出现在前a 礼项，则由命题2 1 2 知s 是( d + 2 h ) 一完全的，即 l n ( s ) ( 扎+ 1 一d 一2 入佗) 2 ， 从而有 其次，若 从而有 再次，若 由归纳知 从而有 综上，可 k ，七( a ( 厂) ) 显然半塑丛专鬻产，从而当 型半些= 坐与兴筹型， ( 2 2 ) 一= 一 iyy i 2 2 f 2 七一1 1 r 一7 ( 2 1 ) 式的右边取得最大值解( 2 2 ) 式可得a = 魁，将其代入( 2 1 ) 式，可得 结论得证 圳a 1 ( 埘必是学型 口 注2 1 1 5p 夕由命题2 1 1 4 可以看出，当错误个数七相对于长度佗很小时，序列a 1 ( ，) 具有 很好的稳定性，即改变一些位置后，序列的恢复难易程度没有显著降低 方法。可 元素取自有限域f 口上的多重序列g = ( s 1 ，s 2 ，s m ) ，其n 次联合线性复杂度定义 为同时生成s 。( 1 让m ) 前n 项的系数在f 口上的最短线性移位寄存器的长度，记为l 竹( 季) 由f 口。和f 孑是k 一线性同构，可以将f 口上m 重序列露等价于元素取自f 。上的单个序列s 则g 的联合线性复杂度即为序列s 的n 一次f 。线性复杂度，即生成5 的系数在f 。上的最短移 位寄存器的长度【1 2 】，记为比p ) 这种等价在证明中有时会带来方便 2 2 1利用函数域构造几乎完全多重序列 作为x i n g 【9 3 】的推广，下面给出利用代数函数域构作多重序列的方法 设f 是f 。上的代数函数域q 为p f 上次数为m 的位，即q 的剩余类域岛笺f 口。取为 q 处的素元且满足d i v ( z ) = q + p d ，其中p 为f 上的有理位，d 是一个次数为m + 1 的 正除子取厂f f 。( ) ，d = d e g ( ( ，) o ) = d e g ( ( ，) o o ) 若峋( ，) o ，考虑，在q 处的局部展开 记 a 1 ( ，) = ( q 1 ，q 2 ，q 3 ，) 若取，y 1 ，倪，为f g m 的一组f 口基，则a 1 ( ，) 可写成 a 1 ( ，) = ( 7 1 ，忱，) 其中口巧f g ，1 i m ，歹1 则 a 1 ( ，) = 匪三 n 1 1口1 20 1 3 0 2 10 2 2n 2 3 口m 1 口m 2 口帕 为f 口上m 重序列 受【9 8 】中证明的启发，我们可以得到上述多重序列的线性复杂度 命题2 2 1 若d = d e g ( ( 厂) o ) = d e g ( ( ，) o o ) ，( ，) o