有限域上定长序列的最短线性递归长度分布

The Distributing Regulation of the Shortest Linear Recurring Length over the Finite Field

研究有限域F(q)上任意给定长度的序列的最短线性递归长度的分布.对任意正整数n和0 l n,计算出了长度为n、最短线性递归长度为l的序列个数,指出了对于固定长度为n的任意序列,其最短线性递归长度大部分情况下等于n/2或n/2+1,即其最短线性递归长度的分布一般都集中在长度的一半位置.

In this paper, when B-M algorithm is applied to search the shortest linear recurring length of single sequence over the finite field F（q）, the distribution of the shortest linear recurring sequence over the finite field F（q） is studied. The amount of the sequences, whose length is n and shortest linear recurring length is l, has been calculated where 0≤1≤n. It is found that the shortest linear recurring length l is always equal to n/2 or n/2 ＋1 for any sequence of length n. In other words, it is always equal to the half of the length of the given sequence.