《环上本原序列保熵压缩映射的研究》由会员分享，可在线阅读，更多相关《环上本原序列保熵压缩映射的研究（82页珍藏版）》请在金锄头文库上搜索。
1、中国人民解放军信息工程大学博士学位论文环上本原序列保熵压缩映射的研究姓名：朱宣勇申请学位级别：博士专业：密码学指导教师：戚文峰20041001信息j 二程大学博士学位论文Y8 2 3 6 5 9致谢首先向我导师戚文峰教授表示深深的谢意。感谢他在我学习和研究工作中的悉心指导与热情鼓励，我所取得的每一点成绩都是导师辛勤耕耘和精心培养的结果。感谢公钥课题组中的老师们，感谢他们给予诸多无私的指导和帮助，尤其是韩文报教授和俞嘉恩教授让我受益匪浅。感谢师弟师妹们，大家在一起组成一个团结的集体，互相帮助，互相鼓励，互相讨论，共度难关，共同提高。因为有了他们，学业途中不再孤独。在攻读博士期间，院、系领导在学习
2、和科研工作上给予了热情的鼓励和巨大的帮助，提供了良好的学习条件和科研环境，使我顺利完成学业。还有许多领导、老师给予我各种形式的帮助和鼓励，在此表示衷心的感谢。本文为国家自然科学基金( 6 0 3 7 3 0 9 2 ) 和全国优秀博士学位论文专项基 _ ( 2 0 0 0 6 0 )资助项目。第1 页共8 1 页信息工程大学博士学位论文中文摘要摘要：设P 是奇素数，整数e 2 ，Z ( p 8 ) 是整数模P 8 的剩余类环环Z ( p 8 1 上序列a 有如下唯一的p - a d i c 分解：垡= _ a o + _ a v p + + 盟一v P 9 1 ，其中璺是 0 ，1 ，p 1
3、) 上序列，称函是序列a 的第i 权位序列，垡是a 的最高权位序列，它们可自然视为素域G F ( p )上序列设删是z ( 矿) 上n 次本原多项式，它是Z ( p 。) 上周期为矿”一1 ) 的首一多项式，并且j ( o ) 0 ( m o d p ) 设 0 ) 是 0 ，1 ，P 一1 上多项式，d e g h ( x ) 0 ，巨= ( 觑f ) ) f o 丰N z = ( “0 ) 。o 都是环R 上序列若对所有非负整数f ，都有0 = O 当且仅当厦O = 0 ，则称序列垡和重的0 元素分布相同，简称为垡和应同O 分布；若对所有满足X t ) o f i q 非负整数f ，都有n
4、 ( f ) = O 当且仅当厦0 = 0 ，则称序列垡和量在z 的控制下同0 性质3 1 设触) 是有限域呱P ) 上“ 次本原多项式，垡，艮G ( ，耻) p ) 都是m 一序列，则( i ) 设g G F p ) 扛】，若它年峨) 互索，则旦和重同O 分布当且仅当g G 地和g O ) 屋同O 分布( i i ) 序列垡和量同0 分布当且仅当存在2 G F ( p ) ，使得垡= 2 巨证明：首先注意到，因为g 与艄互素，所以甄x 垃和颤x ) 重仍是咀触) 生成的m 一序列当”= l 时，G F ( p ) 上的1 级m 一序列中没有0 元素，从而结论是显然的以下我们设”2 因# s
5、A x ) 是G F ( p ) t - 的本原多项式，并且g O ) 和肛) 互素，所以存在非负整数k ，使得x = g O ) ( m o d J ( x ) ) 而垡和里同。分布当且仅当x 和矿尽同。分布是显然的所以结论( i 1 成立注意到，序列垡和重都是电舷) 生成的m 一序列若旦和量同O 分布，则存在整数屯0 蔓k X t ) = a e 一( 0 + 6 。一，( f ) ( r o o d 2 ) ，从而( 3 。1o ) 式成立最后用x 乙1 = 2 h I ) ( m o d 0 ) ) 作用于序列垡和幺类似于( 3 1 4 ) 式，可得x - 1 ) ( 旦2 + 亟)
6、= ( 旦J + b _ O h l ( x ) a _ o + 而I ( 垡l + 查1 ) ( r o o d2 ) 此即为O 。一1 ) ( 缈+ 鱼) = ( q l + 壹1 ) - 3 + _ d ( m o d2 ) r 3 1 9 ) 取f = 翻，由( 3 t t o ) K ，a f t ) = lj 翮= 眈+ b z ( t ) ( r o o d2 ) 又因为弘蚴 丁和p e r ( g ) = t 对于使得须0 = 1 的非负整数t ，有 口2 0 + 即+ b 2 ( t + D 一 a f r o + 6 2 ( 0 】= O ( m o d 2 ) - 若f
7、l ( t ) = 1 ，由( 3 1 9 ) 式，可得氓f ) = 口l ( 0 + 6 l ( 0 ( m o d 2 ) 即以f ) ：麒r ) ：1j 文D ：口l ( ) +6 l ( f ) ( m 。d2 ) 所以( 3 8 ) 成立若3 ( 0 = O ，由( 3 1 9 ) 式，可得文f ) ：0 即a ( 0 ：1 ，f l ( 0 = 0j4 0 = O , q f N ( 3 9 ) 成立( i i ) 当P = 3 时，将x L l = 2 h 1 0 ) ( m 。d m ) ) 作用于序列垡和鱼，类似于( 3 1 4 ) 式，可得( x r - - - 1 ) (
8、 q 2 + 如) = ( 旦l + 鱼1 ) 而l ( 堡o + l ( x ) 妇1 + 查1 ) ( t o o d2 ) ，此即为( x J - 1 ) ( 虫+ 垒) = 乜i + 查f ) 酱+ 耍( m o d2)020)另外，由引理条件，序列a _ 2 和如在垡的控制下同0 对于使得联0 ：1 的非负整数f a 2 ( O = b 2 ( t ) 因为序列垡的周期为tN N a I t + 7 3 = 缸0 = 1 ，进而a 2 ( t + T ) ：b 2 ( + T ) 所以第2 8 页共8 1 页信息工程大学博士学位论文 a 2 ( t + D + b 2 ( t + 即
9、】一 a 2 ( t ) + b 2 ( t ) = O ( m o d2 ) 若觑f ) = 1 ，由( 3 2 0 ) 式，可得文0 = a f r o + 6 l ( 0 ( m o d2 ) 即倒0 = 厦0 = 1j3 ( 0 = a l ( f ) +b f f t ) ( m o d 2 ) 所以( 3 8 ) 成立若f l ( t ) = 0 ，由( 3 2 0 ) 式，可得文，) = 0 即试0 = 1 ，厦0 = 0 j 氓D = 0 所以( 3 9 ) 成立#引理3 4 设翮是z ( 2 。) 上n 次本原多项式，e 3 ，旦，b _ e G ( f ( x ) ，2 e
10、 ) ，垡o g 记垡= h 2 ( x ) a o ( m o d2 ) ，其中 2 如( 2 t 2 ) 式中定义若盟一l 和垒，I 在垡的控制下同0 ，则( i ) 若A 2 C 砷= l ( m o d2 ) ，贝0a _ l + b l = _ a o ( m o d2 ) 或a t = 查l ；若d e g ( h 2 ( x ) m o d2 ) 1 ，贝0 堡1 = 查l ；( i i ) 若旦l = b l ，则序列a k 和甄在垡的控制下同0 ，k = 2 ，3 ，g 一1 ；( i i i ) 若垡l + 查1 = a o ( m o d2 ) ，贝0a + b = 2
11、e - 1 a o ( r o o d 2 e ) 证明：由性质2 2 ，可得h k ( x ) = h 2 ( x ) ( m o d 2 ) ，k 2 所以垡= h e - t ( x ) a o = h e - 2 ) 缅= = h 2 ( x ) a o ( m o d2 ) 同时，我们记唇= h f f x ) _ a o ( m o d2 ) ，巫= 1 0 ) ( 垡l + b 1 ) ( m o d2 ) 假设a I b l ，我们先证明序列竖重和垡l 啦l + _ 8 ( m o d2 ) 在z ，( 2 ) 上两两线性无关因为m ) 是z ( 2 8 ) 上本原多项式，由性
12、质2 2 ，可得 2 0 ) = h i 0 ) ( 1 + l o 。) 0 ( m o d f l x ) ，2 ) ( 3 2 0又因为a _ o e G ( ( x ) ，2 ) 立) ，所以序y t J g = h 2 ( x ) _ a o ( m o d 2 ) = a o 和尽= h i ( x ) a o ( m o d2 ) 是z ( 2 )上线性无关的m 一序列因为_ a l 鱼I ，所以乜I 也O ( m o d2 ) E G ( f ( x ) ，2 ) 、 皿，从而垡1 十鱼+ 点= ( h i ( x ) 十1 ) ( 垡1 + h i ) o ( r o o d
13、 2 ) 此时，我们可断言：区l + b 1 h i ( x ) a o ( m o d2 ) ，旦1 + b l h 2 ( x ) - I h l 2 a 0 ( m o d2 ) ( 3 2 2 )若旦I + 壹1 = h i ( x ) a o ( m o d 2 ) ，则垡l + 鱼I + 耍= ( h i ( 砷+ 1 ) ( 垡l + b 1 ) = h 2 ( x ) a 0 = 旦( m o d2 ) 若a l + b _ l = h 2 ( x ) - lh l ( X ) 2 a 0 ( m o d2 ) ，贝0a _ l + 查l + 变= ( h i ( 砷+ 1 )
14、 ( 垡l + b 1 ) = h L ( x ) a o = 重( m o d2 ) 当缸0 = 厦0 = 1 时，a t ( t ) + b f f t ) + a ( t ) = l ，与( 3 8 ) 式矛盾由( 3 2 1 ) $ I ( 3 2 2 ) 两式，可得力1 0 0 ( 垡+ 旦l + 查l + 毋= h 2 ( x ) 而l O f ) a o + ( 旦l + h i ) 】O ( m o d 2 ) ，矗2 0 0 - 1 I ( x ) 僧+ a l + b l + 国= h 2 ( x ) - L h i 0 0 z g o + ( 旦l + 查1 ) 立( m
15、 o O 2 ) 从而垡+ a l + b l + 查o ( m o d2 ) ，重+ 旦l + 垒l + 变o ( r o o d2 ) 所以序列g 尽和旦1 + 查1 +第2 9 页共8 l 页环上本原序列保熵压缩映射的研究d ( m o d2 ) 是z ( 2 ) 上两两线性无关的m 一序列下面分情形讨论情形I ：h 2 ( x ) = 1 ( r o o d 2 )我f 门证明a l + 查l = a 0 ( m o d 2 ) ，若旦l + 鱼1 a _ o ( m o d 2 ) ，则垡+ 巨+ 旦1 + 查1 + 变= ( h l ( x ) + 1 ) ( 旦o + 旦l +
16、b 1 ) 0 ( m o d 2 ) 由前面的讨论，可知序列g 量和_ a l 地l + 查( m o d2 ) 在Z ( 2 ) - 两两线性无关所以竖盘和盟l 也l + 查( r o o d2 ) 是Z ( 2 ) 上线性无关的m 一序列，从而存在非负整数t ，使得似，) = 1 ，P ( O = l ，a f r o + 6 l ( 0 + 文f ) = 1 这和( 3 8 ) 式矛盾从而垡l + 鱼l = a 0 ( m o d2 ) 所以当h 2 ( x ) = 1 ( r o o d2 ) 时，a _ i = 鱼1 或a 1 + 曼l = _ a o ( m o d 2 ) 情形I I
