一类具有大线性复杂度的非线性过滤函数  

Family of Nonlinear Filter Functions with Large Linear Complexity

作　　者：孙中化[1] 戚文峰[1] 

机构地区：[1]信息工程大学信息工程学院,河南郑州450002

出　　处：《信息工程大学学报》2006年第4期309-313,共5页Journal of Information Engineering University

基　　金：国家自然科学基金资助项目(60373092)

摘　　要：文章指出了论文“A wide family of nonlinear filter functions with a large linear span”存在的问题,给出一个反例,同时得到如下结论:设a是F2上以f(x)为极小多项式的n级m-序列,α为f(x)的一个根,αδ为F2n在F2上的正规元,1≤δ<2n-1。设2≤k≤n-2,令Γ,δk={xδxδ2dxδ22d…xδ2(k-1)d+G(x0,x1,…,x2n-2)|deg(G(x0,x1,…,x2n-2))<k,gcd(d,n)=1},则以Γ,δk中的任意布尔函数作为非线性过滤函数作用在a上得到的输出序列线性复杂度下界为nk。记F2n在F2上的正规元的数量为v(n),则集合{xδxδ2dxδ22d…xδ2(k-1)d|1≤δ<2n-1,αδ为F2n在F2上的正规元,d<n,gcd(d,n)=1}中互异函数的个数为φ(n).v(n)/2。In this paper, we point out the problems in ＂A wide family of nonlinear filter functions with a large linear span＂, give a counterexample, and get the following conclusions： Let a he a binary m-sequence of degree n with minimal polynomial f（x）. Let a he a root of f（x）, and a^δ a normal element in F2^n over F2 ,where 1≤δ〈2^n-1. Let k he a positive integer and 2≤ k ≤ n - 2. Set Гδ,k={xδxδ2^dxδ2^2d…xδ2^（k-1）d＋G（Gx0,x1,…,x2^n-2）｜deg（G（x0,x1,…,x2^n-2））〈k,gcd（d,n）=1} ,then forany F∈Гδ,k ,the linear complexity of the filtered sequence produced by F acting on a is lower hounded by （n k）. Denote the number of normal elements in F2^n over F2 by v （ n）, then the number of different elements in {xδxδ2^dxδ2^2d…xδ2^（k-1）d｜1≤δ〈2^n-1, a^δ is a normal element of F2^n over F2, d 〈 n, gcd（ d, n ） =1} is φ（n） ·v（n）/2.

关 键 词：M-序列 非线性过滤序列 正规元 线性复杂度 

分 类 号：O15[理学—数学]