一类理想自相关序列的伪随机性

一类理想自相关序列的伪随机性 Vol . 31 No . 2 电 子 学 报 第 2 期 ACTA EL ECTRONICA SINICA 2003 年 2 月 Feb. 2003 一类理想自相关序列的伪随机性 胡予濮 ( )西安电子科技大学 ISN 国家重点实验室 ,信息安全研究所 ,陕西西安 710071 要 : 伪随机序列在流密码 、信道编码 、扩频通信等领域有着广泛的应用 . 线性复杂度及其稳定性是序列伪随摘 机性的重要度量指标 . C Ding 等给出了一类具有理想自相关性的周期序列 ,该序列的 0 - 1 分布是几乎均衡的 . 本文讨 论了此类序列的其它伪随机性 . 本文的主要结果如下 :此类序列具有令人满意的线性复杂度 ;在一个符号替换之下此 类序列的线性复杂度不会退化 . 伪随机序列 ; 流密码 ; 线性复杂度 ; 稳定性 关键词 : A () 中图分类号 : TN91811 文献标识码 : 文章编号 : 037222112 20030220245203 P s e udo2Ra ndo mne s s of a Cla s s of Se que nc e s wit h Ide al Auto co rrelatio n HU Yu2pu ( ) IS PI , ISN National Key L ab . , Xidian University , Xi’an , S haanxi 710071 , China Ab stract : Pseudo random sequence has broad applications in stream cipher , channel coding , and spread spectrum commun2i cation. Linear complexity and its robustness are important features of pseudo randomness. C Ding presented a novel class of sequences with ideal autocorrelation and almost balanced 0 - 1 distribution. This paper discusses other pseudo2randomness of such sequences. The major results are the following : such sequences have quite satisfactory linear complexities ; their linear complexities do not degenerate under single symbol substitution. Key word s : pseudo2random sequence ; stream cipher ;linear complexity ; robustness [1,8 ] 点, 但一个重要问题是讨论理想自相关序列的其它伪随 1 引言 () GF 2上的伪随机序列具有极为广泛的应用 ,比如流密 机性能 , 包括线性复杂度 、多维分布 、游程分布等 . 在现有的理 n 码 、信道编码 、扩频通信等等 . 评价一个伪随机序列优劣的基 想自相关序列中有以下事实 :最小周期为 2 - 1 的 m 序列具 本准则是伪随机性 . 我们用许多指标来描述一个周期序列的 有良好的多维分布和游程分布 , 但最小的线性复杂度 n ; 最小 伪随机性 ,比如大的周期 、大的线性复杂度 、均衡性 、良好的自 n [9 ] [10 , 11 ] 周期为 2 - 1 的 GMW 序列或广义 GMW 序列, 同样具 相关性 、稳定性等等 . 所谓良好的自相关性指的是自相关函数 有良好的多维分布和游程分布 , 但其线性复杂度也仅仅为 n 的绝对值一致地小 . 自相关函数定义为 的幂 ; 以 Mersenne 素数 p 为最小周期的 Legendre 序列具有很 [ 12 ] 好的多维分布和 游 程 分 布, 且 线 性 复 杂 度 与 p 为 同 阶 大 ) (( ) 定义 1 设 GF 2= 0 , 1 , 2 ,s tt } , 其上的周期序列{ , [13 ] 数; 其它各类理想自相关序列的伪随机性能尚不清楚 . 最小周期为 N . 称N - 1 理想自相关序列的另一个重要问题是稳定性 , 比如在有 ( ) ( )t + w- s t s( ) ( ) , w = 1, N - 1Cw= - 1 s ? 传输差错时其各种伪随机性能不应退化 . 最近文献 [6 ]给出了 t - 0 一类具有理想自相关性的周期序列 , 且该序列的 0 - 1 分布是 ( ) 为序列{ s t, t = 0 , 1 , 2 , } 的自相关函数 . [ 14 ] 几乎均衡 的 . 此 类 序 列 是 Legendre 序 列 和 对 数 序 列的 变 希望自相关函数的绝对值普遍较小 . 令 w 遍取 1, N - 形 . 本文讨论了此类序列的其它伪随机性和稳定性 . 主 要 结 ( ) ( ) 1 , 容易得到以下结论 :当 N ?- 1 mod 4时 , Cw的可能取 s 果 :此类序列的线性复杂度令人满意 , 为最小周期的同 阶 大 ( ) ( ) 值在{ - N - 2, - N - 6, , - 1 , 3 , , N - 4} 范围内 ; 当 数 ; 在一个符号替换之下此类序列的线性复杂度不会退化 . ( ) ( ) ( ) ( ) N ?1 mod 4时 , Cw的可能取值在{ - N - 2, - N - 6, s ( ) ( ) , - 3 , 1 , , N - 4} 范围内 ; 当 N ?2 mod 4时 , Cw的可 s 2 一类理想自相关序列及其线性复杂度62 2 ( ) 能取值在{ - N , - N - 4, , - 2 , 2 , , N - 4} 范围内 ; 当 N 2 定义 设素数 p 满足 p = 4 f + 1 = x+ 4 y, 其中 x ?1 4 ( ) ( ) ( ) ?0 mod 4w- N , - N - 4, - 4 , C时 , 的可能取值在{ , s ( ) (α) ( ) αmod4. 取定 GF p上的本原元 , 记乘法子群 D= ; 记 0 j 0 , 4 , , N - 4} 范围内 . 因此如果出现以下四种情形之一 :α陪集 D= D, j ?{ 0 , 1 , 2 , 3} . 取定三个整数 i , j , l , 它们互不 j 0 () ( ) ( ) ) ( ( 1N ?- 1 mod 4, 且恒有 Cw = - 1 ; 2N ?1 mods ( ) 相同 , 且均取值于{ 0 , 1 , 2 , 3} . 定义序列{ s t, t = 0 , 1 , 2 , } 如 ) ( ) ) ( ) ( ) (4, 且恒有 Cw= 1 ; 3N ?2 mod 4, 且恒有 Cw= ?2 ; s s ( ) ( ) ( ) 下 :在以下四种情形 s t= 1 , 否则 s t= 0 : t 偶且 t mod p? () ( ) ( ) 4N ?0 mod 4, 且 Cw?{ - 4 , 0 , 4} ; s ( ) ( ) ( )D; t 偶且 t mod p?D; t 奇且 t mod p?D; t 奇且 t mod p i j l ( ) 就称周期序列{ s t, t = 0 , 1 , 2 , } 为一个具有理想自相 ?D . j 关性的序列 . 寻找具有理想自相关性的序列是理论研究的热 6 定理 1 收稿日期 :2001208217 ;修回日期 :2002208225 (() )基金项目 : ISN 国家重点实验室开放课题基金 No15 - 03;武器装备预研基金 No151436010201DZ0104 m ) (( ) 1定 义 2 给 出 的 序 列 { s t } 最 小 周 期 为 2 p , 且 | { t | β) (S ?0 , 则由引理 2 和引理 3 有 mk ( ) s t= 1 , t = 0,2 p - 1} | = p - 1 ;β) ( S ?0 , k ?D ;() 0 , 12 mu mu 2 ( () ) () ( ) ( ) 2设 y = 1 , f 奇 , i , j , l= 0 , 1 , 3或 0 , 2 , 1, 则{ s t }(β) β) (S = S ?0 , u ?D ; S () 0 , 14 mv mv 4 8 是理想自相关序列 ;(β) β) β((= S ?0 , v ?D ; S () 0 , 1() () ( ) ( ) ( ) 3设 x = 1 , f 奇 , i , j , l= 1 , 0 , 3或 0 , 1 , 2, 则{ s t }mw mw 8 ) β) (= S ?0 , w ?D . () 0 , 1 是理想自相关序列 .注意到{ mk| k ?D()} 、{ 2 mu| u ?D)} 、{ 4 mv| v ?D)} 、(( 0 , 1 0 , 1 0 , 1 ( ) 引理 1 记 D = { t | t = 1, 2 p - 1 , t 奇 , t mod p?() 0 , 1m β) ({ 8 mw| w ?D } 关于模 p 互不同余 , 因此{ S | m = 0, p () 0 , 1( ) D} , 则 ?| D | = p - 1/ 4 ; ?对任何 t , 任何 n ?D , s() () 0 0 , 10 , 1 - 1} 中非 0 元的个数是 4| D | 的非 0 倍数 . 类似于定理 2() 0 , 1( ) ( ) nt= 1 当且仅当 s t= 1.( ) ( ) 的证明过程 , 序列{ s t} 的极小多项式 g X的次数不小于 8) ( 证明 ?显然 . 为证 ?, 只须注意到 : nt ?t mod2, nt ?( ) | D ()| = 2 p - 1. 定理 3 得证 . 0 , 1 ( ) t mod p. 引理 1 得证 .( 推论 如果 2 是模 p 的二次剩余但非四次剩余 注意到 β 引理 2 设 为 2 特征域上的一个 p 阶元 . 记 X 的多项) ( ) 此时 f 是偶数, 则由定义 2 给出的序列{ s t } 线性复杂度不 2 p- 1 t ( ) 小于 p - 1. ( ) ( ) S X = s t X. 则 对 任 何 整 数 m , 任 何式 k ?D , (0 , 1) ? t - 0 证明 从上知道 , 此时因 1 、2 分别属于 D的不同陪集 .0 m mk β) β) ((S = S . m mk β) β) (( 取定 m 使得 S ?0 , 则由引理 2 和引理 3 有 : S ?0 , k 证明 首先对于固定的 k ?D , 存在唯一的 n , 1 ?n() 0 , 12 mu mu 2 β) β) ) ((?D ; S = S ?0 , u ?D .() (0 , 10 , 1 ( ) ?2 p - 1 , 使得 kn ?1 mod2 p. 其次有 n ?D . 因此由引理() 0 , 1 注意到{ mk| k ?D } 、{ 2 mu| u ?D } 关于模 p 互不(() ) 0 , 10 , 1 1 得m β) ( 同余 , 因此集合{ S | m = 0, p - 1} 中的非 0 元的个数是mk mt mkt β) (S = ββ=?? ( ) ( ) t = 0,2 p - 1 ; s nt= 1t = 0,2 p - 1 ; s t= 1 ( ) 2| D ()0 , 1 | 的非 0 倍数 . 类似于定理 2 的证明过程 , 序列{ s t } mt m = ββ)(= S ?( ) t = 0,2 p - 1 ; s t= 1( ) ( ) )的极小多项式 g X的次数不小于 4| D , | = p - 1. 推论 (0 1 引理 2 得证 . 得证 . β( )引理 3 设 为 2 特征域上的一个 p 阶元 , 多项式 S X 3 线性复杂度的稳定性 如引理 2 所示 . 则集合β( ) 以下总设 为 2 特征域上的一个 p 阶元 , 多项式 S Xm β) ( { S | m = 0, p - 1} 如引理 2 所示 .( ) 中的非 0 元的个数是 p - 1/ 4 的非 0 倍数 .m β ) (引理 4 集合{ S | m = 0, p - 1} 中的所有元素均满 0 β) (( ) 证明 首先由定理 1 , S = | { t | s t = 1 , t = 0,2 p -m 16 m β ) (β ) (= S 足 S . m ( ) β) (1} | mod2= 0. 其次集合{ S | m = 0, p - 1} 中的元素不全 m m β) β) ((证明 当 S = 0 时结论正确 , 以下设 S ?0 , 我们 为 0 元 , 否则有 m 2 m m 4 ( β ) β ) β ) ) (((知道此时 m ?0 mod p. 当 S = S , 或 S = p- 1 m m 8 m mt β) β) β) ((( ( ( ) β( ) )S ,或 S = S 时 结 论 正 确 . 以 下 设 m 使 得 Ss t+ s t + p= 0 , m = 0, p - 1? t - 0 m m 2 m 4 m 8 (β ) β ) β ) β ) (((、S 、S 、S 互不相等 . 注意到以下事实 : p- 1 t mk m ( ( ) ( ) ) 即 X 的多项式 s t+ s t + pX的系数全为 0 ; 换句话β) β) ((; S = S , k ?D ()0 , 1 ? t - 0 2 mu mu 2 2 m β) β) β) (((= S = S , u ?D ; S (0 , 1) ( ) 说 , 序 列 { s t } 最 小 周 期 为 p , 与 定 理 1 矛 盾 . 最 后 注 意 到 4 mv mv 4 4 m β ) β )(β (() S = S = S , v ?D ; () 0 , 1 D 中的数关于 mod p 互不同余 , 故由引理 1 和引理 2 , 集合() 0 , 18 mw mw 8 8 m m (β) β) β) ((S = S = S , w ?D . (0 , 1) (β) ( ) { S | m = 0, p - 1} 中的非 0 元的个数是| D 0 , 1| 的非 0( ) ( ) 因此 四 个 集 合 { mk mod p| k ?D } ; { 2 mu mod p| u ? () 0 , 1 倍数 . 引理 3 得证 .( ) ( ) D } ; { 4 mv mod p| v ?D } ; { 8 mw mod p| w ?D } 必 () () () 0 , 10 , 10 , 1( ) 定理 2 由定义 2 给出的序列{ s t } 线性复杂度不小于( ) 须互不相交 . 又因为其中每个集合的元素个数为 p - 1/ 4 , 故 ( ) p - 1/ 2. ( ) ( ) { mk mod p| k ?D } ?{ 2 mu mod p| u ?D }() () 0 , 10 , 1β( ) 证明 设 为一个 p 阶元 , 我们知道序列{ s t } 的极小 ( ) ( ) ?{ 4 mv mod p| v ?D } ?{ 8 mw mod p| w ?D }(() ) 0 , 10 , 1 多项式为= { 1 , 2 , , p - 1} 2 p p 2 () X 1 - X 1 - ( ) g X= = 2 p p2 m 16 m 2 m (( () ( ) ) ( ) )gcd 1 - X, S Xgcd 1 - X, S X β) β) β) (((综合 以 上 事 实 , S 必 须 等 于 S 、S 、 p - 1 4 m 8 m m β ) β ) β ) (((p2 m 2 m m 2 S 、S 中的一个 . 又因为 2 与 S 的阶互素 , 故只 () ( ( β) ) (β) β) ( 1 - X= X - . 当 S ?0 时 , X - | g而 ? m 16 m m = 0 β) β) (( 能有 S = S . 引理 4 得证 .( ) ( ) ( ) X. 由引理 3 , g X的次数不小于 p - 1/ 2. 定理 2 得证 . 3 d ( ) ( ) 定理 4 设 p > 15 , S X= S X+ X, 0 ?d ?2 p - 1 ,定理 3 如果素数 p = 4 f + 1 , f 奇 , 则由定义 2 给出的序 3 m (β) 且 d ?0 , d ?p. 则{ S | m = 0, p - 1} 中都是非 0 元 , 因( ) ( ) 列{ s t} 线性复杂度不小于 2 p - 1. 2 p 1 - X2 p X . 此有= 1 -2 p 3 证明 我们知道此时 2 不是模 p 的二次剩余 , 因此 1 、2 、 (( ) ) gcd 1 - X, S X3 m ( ) 4 、8 分别属于 D的不 同 陪 集 见 定 义 2. 取 定 一 个 m 使 得(β) 0 证明 当 m = 0 时 , S = 1 ; 当 m = 1 , p - 1 时 , 第 2 期胡予濮 :一类理想自相关序列的伪随机性247 3 m m md m 3 3 d 3 3 m (β) β) ββ) ( ((S = S +, 其中 S 的阶是 15 的因子 见引理 ( ) (β) ( ) X= S X+ X, d = 0 或 d = p. 则{ S | m = 0, p S md3 m 2 p ) β(β) 4,的阶为 p , 故 S ?0. 定理 4 得证 .1 - X2 p - 1} 中都是非 0 元 , 因此有= 1 - X . t m 2 p 3 3 () )1 - X , S (X gcd β ) (( ) X . 则 S =引理 5 取定多项式 h X = ? t ?D ?D i l 3 3 0 m (β) 证明 总有 S = 1. 当 m = 1, p - 1 时 , 由引理 7 β) (h , m = 0, p - 1. m m2 m (β ) (β ) (β) 和引 理 8 知 S ? S , 因 此 S ?1. 这 说 明 0 0 β) β) ((证明 S = h = 0. 对于 m = 1, p - 1 , 3 3 m (β) S ?0. 定理 5 得证 . m mt mt mt m β) ββββ)((= +== h S ??? t ?D?Dt ?D ?Dt ?D ?D由定理 4 和定理 5 说明 , 当有一个符号替换时 , 序列的线 j l j i l i 性复杂度增加到 2 p. 引理 5 得证 . m m 2 ( ) β) (β) ( 4 一点说明引理 6 取定定理 1 的 2情形 . 则{ S + S , mm m 2 β) β) (( = 0, p - 1 } 有 两 种 可 能 的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达 方 式 : S + S =我们未能证明定义 2 所给出的序列的良好多维分布和良 2 m mt mmt 好游程分布. 不过由于此类序列的构造有点像 Legendre 序列 , β ) β ) ((β或 S + S = β.?? t ?D ?D t ?D ?D0 2 1 3 猜想其多维分布和游程分布较好. 以下给出了此类序列似乎具 ( ) 证明在定理 1 的 22 ?D或 2 ?D. 以下情形 , 必有 1 3 有其它良好伪随机性能的一个证据 :将序列进行等间隔采样 , 分为四种子情形来分别证明 : m , m 与 2 和 p 均互素. 则当 m ?D 时 , 采样序列间隔长度为 0 ( ) () ?i , l= 0 , 3, 2 ?D. 由引理 5 , 此时1 仍然是原来序列的平移序列 ; 当 m 属于其它的 D 时 , 采样序 k m m 2 m 2 m mt β) β) β) β) β((((S + S = h + h = ?( ) 列仍然是形如定义 2 的序列 ,只不过对应的 i , j , lt ?D ?D 改变了. 0 3 mt mt 参考文献 : β+ β=;?? t ?D ?D t ?D ?D1 0 1 3 1 A Chang ,S W Golomb , G Gong , P V Kumar . On ideal autocorrelation ( ) () ?i , l= 0 , 3, 2 ?D. 此时 3 sequences arising from hyperovals A . in Sequences and Their Appli 2 mt m m 2 m 2 m ββ) β) β) β) ((((S + S = h + h = ? t ?D ?D 0 3 cations : Proc . SETA’98 C. U K: Springer 2Verlag ,1999 . 17 - 38 . mt mt 2 J A Davis. Almost difference sets and reversible difference sets J . + ββ=;?? t ?D ?D t ?D ?D3 2 0 2 Arch. Math. ,1992 ,59 :595 - 602 . ( ) () ?i , l= 0 , 1, 2 ?D. 此时 1 3 C Ding ,T Helleseth , K YLam. Several classes of binary sequences with m m 2 m 2 m mt β) β) β) β) ((((S + S = h + h = β? three2level autocorrelationJ . IEEE Trans. IT ,1999 ,45 :2601 - 2606 . t ?D ?D 0 1 mt 4 mt J - H Kim , H - Y Song. Existence of cyclic Hadamard difference sets β+ β=;?? t ?D ?D t ?D ?D1 2 0 3 and its relation to binary sequences with ideal autocorrelation J . J . ( ) () ?i , l= 0 , 1, 2 ?D. 此时 3 () Commun. And Networks ,1999 ,1 1:14 - 18 . m m 2 m 2 m mt β) β) β) β) ((((β5 S + S = h + h = A Lempel , et al . A class of binary sequences with optimal autocorre2 ? t ?D ?D 0 1 () lation propertiesJ . IEEE Trans. IT ,1977 ,23 1:38 - 42 . mt mt =β+ β.?? t ?D ?D t ?D ?DC Ding ,et al . New families of binary sequences with optimal three2level 6 3 0 1 3 () 引理 6 得证 . autocorrelationJ . IEEE Trans. IT ,2001 ,47 1:428 - 433 . 7 J - S No , H Chung ,M - S Yun. Binary pseudorandom sequences of () 引理 7 取定定理 1 的 2情形 . 则有 :n 0 0 2 m m 2period 2- 1 with ideal autocorrelation J . IEEE Trans. IT , 1998 , 44 (β) β) β) β) (((S = S ; 当 m = 1, p - 1 时 , S ?S 0 0 2 () 2:814 - 817 . β) β) (( 证明 S = S = 0 是已知的 . 由引理 6 , 当 m = 1J - S No , H Chung ,M - S Yun. Binary pseudorandom sequences of 8 , p - 1 时无论如何都有m d (period 2 - 1 with ideal autocorrelation generated by polynomial z + z m m 2 m m 2 2 mt (β) (β) ( (β) (β) ) S + S + S + S = β? t ?D ?D d 0 2 ) () + 1J . IEEE Trans IT ,1998 ,44 3:1278 - 1282 . p- 1 9 R A Scholtz ,L R Welch. GMW sequencesJ . IEEE Trans IT ,1984 ,30 mt mt ββ+ == 1 ?? t ?D ?D 1 3 () t = 1 3:548 - 553 . m m 2 β) β) ((这说明 S + S ?0. 引理 7 得证 . 10 J - S No . Generalization of GMW sequences and No sequences J . 0 0 2 () IEEE Trans IT ,1996 ,42 1:260 - 262 . ( ) (β) (β) 取定定理 1 的 3情形 . 则 S = S = 0 ; 引理 8 m m 2 Andrew Klapper ,A H Chan ,Mark Goresky. Cascaded GMW Sequences 11 β) β) ((S + S = 1 , m = 1, p - 1. () J . IEEE Trans IT ,1993 ,39 1:177 - 183 . ( ) () ( ) 因为 i , l= 1 , 30 , 22 ?D或 D, 故由证明 或 , 且 1 3 12 I Damgaard. On the randomness of Legendre and Jacobi sequencesA . 引理 5 ,Advances in Cryptology2CRYPTO’88 C . S. Goldwasser , Ed. Berlin , m m 2 mt mt β) β) ββ((S + S = +?? t ?D ?Dt ?D ?D 0 2 1 3 Germany ,Springer2Verlag ,1990 . 163 - 172 . p - 1 Cunsheng Ding ,Tor Helleseth ,Weijuan Shan. On the linear complexity 13 mt β= = 1 ,m = 1, p - 1 ? () t = 1 of legendre sequencesJ . IEEE Trans IT ,1998 ,44 3:1276 - 1278 . 引理 8 得证 . 14 Yupu Hu , Guoqiang Bai , Guozhen Xiao . On logarithmic sequencesJ . () ( ) ( ) Chinese Journal of Electronics ,2000 ,9 4:479 - 480 . 定理 5 取定定理 1 的 2情形或定理 1 的 3情形 . 设