Bent序列簇的迹表示的进一步研究.doc

Bent 序列簇的迹表示的进一步研究 柯品惠 1 张劼2 温巧燕2 1 福建师范大学 网络安全与密码技术重点实验室 福建 福州 350007 2 北京邮电大学 理学院 北京 100876 摘 要 满足一定条件的线性满射是生成 Bent 序列簇的重要部分 对此进行了进一步研究 完全刻画了所有的 生成 Bent 序列簇所必需的线性满射 完善了已有的结果 关键词 Bent 序列簇 Bent 函数 有限域 中图分类号 TN918 1文献标识码 A文章编号 1000 436X 2007 05 0118 04 Further study of the trace representation of Bent sequences families KE Pin hui1 ZHANG Jie2 WEN Qiao yan2 1 School of Mathematics and Computer Science Fujian Normal University Fuzhou 350007 China 2 School of Science Beijing University of Posts and Telecomunications Beijing 100876 China Abstract Linear onto mapping satisfying certain conditions plays an important role in the generation of Bent sequences families Further discussions were made A well rounded characterization of these mapping were presented and known results were showed to be a subcase of our general results Key words Bent sequence families Bent functions finite fields 1 引言 1 自 1982 年 Olsen Scholtz 和 Welsh 1 提出 Bent 序列簇 简称 OSW 序列簇 以来 由于其具 有低相关特性等良好性质 在通信系统中有重大 的应用 由此引起了众多学者的关注 2 3 线性满 射是生成 OSW 序列簇的一个重要部分 然而长期 以来 对其构造中使用的线性满射并未给出一个 具体的表达式 文献 4 首次通过分析线性满射所 满足的条件给出一个具体的表达式 进而给出 OSW 序列簇的迹表示 我们对此进行了进一步的 研究 给出了满足条件的全部解 进而刻画了所 有可能的满足条件的线性满射 结果表明文献 4 收稿日期 2006 03 20 修回日期 2007 01 30 中给出的满足条件的线性满射的表达式只是我们 解的一部分 进而说明文献 4 中用迹表示的 OSW 序列簇只是全部 OSW 序列簇的一部分 2 基本定义和概念 设 n F2是特征为 2 阶数为 2n的有限域 m m n m xxxxtr n m 1 22 是 n F2到 m F2的迹 函数 n F2表示二元域 F2上的n维向量空间 设布 尔函数 22 FFxf n 由 n F2和 2 n F同构 也 可以等价地考虑 n F2到 n F2的函数 在不引起混淆的 情 第 28 卷第 5 期通 信 学 报Vol 28 No 5 2007 年 5 月Journal on CommunicationsMay 2007 基金项目 国家高技术研究发展计划 863 计划 2006AA01Z419 国家自然科学基金重大研究计划资助项目 90604023 教育部博士点基金资助项目 20040013007 福建省青年人才项目 2006F3044 Foundation Items The National High Technology Research and Development Program of China 863 Program 2006AA01Z419 The National Natural Science Foundation Major Project of China 90604023 The Ph D Program Foundation of Ministry of Education of China 20040013007 Fujian Province Young Talent Program 2006F3044 第 5 期柯品惠等 Bent 序列簇的迹表示的进一步研究 119 况下 本文统一用 来表示 n F2和 n F2的加法 设 22 FFxf n 称 2 2 1 n f xx wn x F fF 为 f 的 Walsh 变换 w f为 f 在 的谱值 称 f 的非线性度为 minlfdN n Alf 这里 n A是 n F2上所有仿射函数的集合 可以用 Walsh 谱来刻画f的非线性度 即 max 2 1 2 1 wn f fN 由 Parseval 公式 5 知 Nf有最大值 1 2 1 22 n n 此 时 2 2 n w f 且n必须为偶数 定义 5 若n为偶数 且对任意的 n F2 2 2 n w f 则称 f 为 Bent 函数 Bent 函数是布尔函数中很重要的一个函数类 它在编码 密码以及本文后面所讨论的序列设计 中都有广泛的应用 关于它的研究成果非常丰富 有兴趣的读者可以参看文献 5 6 及其后面的参考文 献 3 Bent 序列簇的迹表示 本节给出主要结果 其中涵盖了文献 4 中给 出的结果 OSW 序列簇构造如下 1 设 4 mod0 n且 222 0 2 mmn FFFxmn L是 n F2到 m F2的线 性满射且满足 2 0 m FxLrange 令 xf是 m F2到 F2的 Bent 函数 则序列簇 2 022 mn z Ss tzFt 2 022 mn z Ss tzFt 定义为 T 1 ttnt z s tf LLztr 这里 是 n F2的一个本原元 由上面的构造中可以看出 OSW 序列簇主要由 线性满射和 Bent 函数来生成 但是对满足如上条 件的线性满射长期以来一直没有给出一个明确的 表达式 文献 4 对此做了研究 他们利用了 m F2和 m F2 是同构的 等价地考虑了满足如上条件的 n F2到 m F2的线性满射 给出如上线性满射的表达 式 进而给出了 OSW 序列簇的迹表示 m F2和 m F2 的同构是通过取 m F2上的一组基 来实现的 不妨设 21m 是 m F2在 F2 上的一组自对偶基 8 即 1 1 0 m ij ij tr 若 其他 引理 1 设 T x 是 m F2上的变换 对于 m Fbai ii m 2 12 2 1 且 ii ba 又 212 21 mm Fbbb 212 21 mm Fbbb 不妨设 21m bbb 就是 m F2在 F2上 的一组自对偶基 若 12 2 1 11 m i m ii m ixTbtrxbatr 1 对所有的 m Fx 2 成立 则 对 12 2 1 m j j a和 j b有如下关系 若 j b在如上的自对偶基下可以表示为 1 m i iij btb 2 Fti F2 则 i m i ij ata 1 而且 1 m i i T xb 1 m ii trab x 进一步地 若 T x 是 m F2上的置换 则 i a 1im 还必须满足 2211mm bababa 也是 m F2在 F2上的一组 基 证明 首先证明 T 是线性的 由 11 11 mm iii mm iiii trbT xytrabxy trab xtrab y 11 1 mm ii m i trbT xtrbT y trb T xT y 对任意的 2 m i bF 及 2 m x yF 成立 即 1 0 m i trb T xyT xT y 对任意的 2 m i bF 成立 所以对任意的 2 m x yF 有 T xyT xT y 即 T 是线性的 不妨设 1 m ii i T xT x b 则 11 1 2 mm iiii T xtrbT xtrab x im 记 iii cab 则 1 1 2 m ii T xtrc x im 所以有 1 1 m m ii i T xbtrc x 120 通 信 学 报第 28 卷 设 2 1 m jiii i bt b tF 11 111 mmm mm jiiiiii iii trb T xtrt bT x btT x 11 11 mm mm iiii ii t trc xtrt c x 又 111 mmm jjjj trb T xtrab xtrc x 从 而 11 1 m mm iij i trt c xtrc x 对任意的 2m xF 成立 所以 1 m jii i ct c 即 1 m jjiii i abt ab 又 1 m jii i bt b 因此 1 m jii i at a 若 T x还是 2m F上的置换 由 1 1 m m jiij i T bbtrcb 知 T 是 2m F上的置换当且仅当如下的矩阵 11 111 211 12 112212 11121 mmm m mmm m mmm mmmm trbctrbctrbc trb ctrb ctrb c trb ctrb ctrb c 是满秩的 而上面的矩阵的每一列恰好是 i c在基 12 m b bb 下的坐标 从而上述矩阵满秩当且仅 当 12 m c cc 也是 2m F上的一组基 证毕 注 由引理 1 知 要使得引理条件中的一系 列方程成立 i a和 i b 必须满足一定的关系 若 1 m ii b 是 2m F的一组自对偶基 此时 j a 和 j b 有同样 的线性表示 即 j a由 1 m ii a 和 j b 在 1 m ii b 下的坐标 确定 特别地 由文献 4 中的讨论知 我们特别 关注的是在 T 是 2m F上的置换的情形 此时 i a和 i b 的选取更加严格 必须满足 1 m iii ab 也是 2m F在 2 F上的一组基 推论 1 4 设 T x是 2m F上的变换 对于 2 1 2 21 m m ii ia bF 且 ii ab 又 12 212 mm b bbF 12 212 mm b bbF 则 111 111222 212121 mmm ab bab babb 且 1 111 T xab b x 是满足如上引理 1 中式 1 的 特解 证明 不妨设 1 1 2 21 m iii ab bc i 即 iiii cabcb 由 1 m ii b 是 2m F的自对偶基 易知 此时 1 m ii c 亦是 2m F上的一组基 由引理知 T x是 2m F上的线性置换 此时 1 1 m m ii i T xbtrcb x 记 1 m ii i cxt b 则 1 1111 111 mmm m iiiiii iii T xbtrbt bt bcxab b x 这说明了文献 4 中的结论只是全部可能解的一部 分 定理 设 l x是 2n F 到 2m F的线性满射 0 22 nm xFF 0 2 m range lxF 则 2 0 n m l xtrx xxx 其中 x 是 2n F 到 2m F的函数 满足 2 xx 和 0 n m trx x 有 同样的线性关系 而且若 01 nm mii trx x 是 m F2在 2 F上的一组自对偶基 则 2 01 nm miiii trx xxx 也是 2m F在 2 F上的一组 基 证明 由文献 4 中定理 1 的证明知 存在 2n F 到 2m F的函数 x 使得 2 0 n m l xtrx xxx 而且存在 2m F上的置换 T 使得 2 1010 mnmn mm trz trx xxxtrT z trx x 首先由 l x和 0 n m trx x 都是线性的 易知 2 xx 也是线性的 而且 2 xx 和 0 n m trx x 有同样的线性关系 然后再把 0 n m trx x 看 作 i b 2 xx 看作 i a 从而由引理 1 定理 证毕 由定理得知 满足条件的线性满射是相当多 的 文献 4 中给出的 2 0 n m xxc trx x 0 1 n m l xctrx x 只是所有可能的线性满射的特 例 从而文献 4 中用迹表示的 OSW 序列簇只是所 有可能的 OSW 序列簇的一部分 当然从已有的结 果来看 为了快速生成 OSW 序列簇 我们可以选 第 5 期柯品惠等 Bent 序列簇的迹表示的进一步研究 121 取文献 4 中用给出的满足条件的线性满射 而其 中的 Bent 函数可以选取用迹函数表示的 Bent 函数 如文献 7 中给出的用迹函数表示的二次 Bent 函数 来快速生成 OSW 序列簇 4 结束语 OSW 序列簇是很有应用价值的一类序列簇 它主要通过线性满射和 Bent 函数来生成 文献 4 首次对其中的线性满射进行了研究 给出其具体 的表达式 进而给 OSW 序列簇的迹表示 本文对 其进行了进一步的研究 比较完整地刻画了满足 条件的线性满射 完善了已有结果 另一方面 从我们对满足条件的线性满射的刻画得知 能简 单地用迹函数来表示的只是其中一部分 对其他 一般的情形是否有更简单的表示还有待做进一步 研究 参考文献 1 OLSEN J SCHOLTZ R WELCH L Bent function sequences J IEEE Trans Inform Theory 1982 28 6 858 864 2 LEMPLE A COHN M Maximal families of Bent sequences J IEEE Trans Inform Theory 1982 28 6 865 868 3 NO J S GIL G M SHIN D J Generalized construction of binary Bent sequences with optimal correlation property J IEEE Trans Inform Theory 2003 49 7 1769 1780 4 王劲松 戚文峰 Bent 序列簇的迹表示 J 通信学报 2006 27 1 8 13 WANG J S QI W F Trace expression of Bent sequence families J Journal on Communications 2006