《利用代数曲线构造序列和码》由会员分享，可在线阅读，更多相关《利用代数曲线构造序列和码（92页珍藏版）》请在金锄头文库上搜索。
1、B y D I N GY a n g S u p e i s e db y P r o f C H E NJ i a n l o n g P r o f X I N GC h a 舻p i n g 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 y A p r i l2 0 1 0 o M 研究生签名：! 冱日期：主竺丝：垒：1 2 3 东南大学学位论文使用授权声明 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印，缩印或其他复制
2、手段保存论文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 _ 蛘 研究生签名： 过2 主 导师签名： 日期幽够，2 ，) 日期：塑! ：兰：7 数 造 密 这 两个问题吸引了很多人的关注本文主要利用有限域上平面代数曲线的算术理论( 代数函 数域理论) 来研究这两个热点问题 在流密码体系中，密钥流序列是元素取自有限域的伪随机序列为了抵抗B e r l e k 锄p - M a s s e y 算法攻击，首先需要构造具有高线性复杂度的密钥流序列同时基于对密码
3、稳定 性的考量，还需要构造具有高错误线性复杂度的密钥流序列 对于非周期序列的情形，X i n g - L 锄利用函数在有理位的局部展开给出了单个非周期 序列的构造，本文给出了X i n 乎L a m 构造的单个非周期序列的错误线性复杂度的一个下界， 并把n g 利用函数局部展开得到多重序列的构造推广到更一般的情形对这样得到的多 重序列，本文同样给出了其联合错误线性复杂度的一个下界 对于周期序列的情形，将) ( i n g - D i n 乎K 啪a r 关于单个序列的构造推广到多重序列的 情形，并证明这样得到的多重序列其联合线性复杂度及错误联合线性复杂度都可以很高 此外，基于函数域的自同构群的
4、结构，利用函数域上函数在高次位的赋值及在有理位的赋 值，给出多重周期序列的两种新的构造方法分析并证明了当函数满足一定的条件时，这 样得到的多重周期序列的联合线性复杂度和错误联合线性复杂度可以达到最大值，即等 于周期特别地，利用H e m i t i a n 函数域的相关性质，构造出三类多重周期序列证明了当 错误个数小于重数减2 时，其错误联合线性复杂度可达到多重序列的周期 在纠错码码字个数的渐近界方面本文考虑两类特殊的码：常重复合码和二元自正 交码对于常重复合码，本文利用剩余多项式环给出常重复合码的一个构造当固定最 小距离d 和码长n 时，此构造给出了的常重复合码最大码字个数A 。( n ，d
5、 ，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
6、 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
7、 的 一个公开问题此外，利用代数函数域的自同构在有理位集合上的作用给出了拟循环码的 构造特别地，在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
8、 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
9、 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
10、 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
11、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
12、 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
13、 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 t
14、h 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
15、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
16、 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
