Galois环导出p元序列中元素组的分布及其渐近均匀性

Distribution of r-grams in p-ary sequences derived from sequences over Galois rings and the asymptotical uniformity

r-样式的分布是有限域上序列伪随机性的一个重要方面。就此问题本文对域R/pR上一类序列作了考察,这类序列得自于Galois环R=GR(ptn, pn)上其特征多项式f (x)在模p下本原的线性递归序列(包括极大长序列)的p-adic展开,即所谓Galois环导出p元序列。我们得到了这种序列上独立r-样式分布的一个估计,作为推论,r-样式的分布关于f (x)的次数是渐近均匀的。

Distribution of r-grams is an important aspect of pseudo-randomness for sequences over a finite field. In this paper this problem is investigated for sequences over the field R/pR derived from the p-adic expansion of some linear recursion sequences (including maximal length sequences) over the Galois ring R=GR (ptn, pn), whose characteristic polynomial f (x) is primitive modulo p. An upper bound of the deviation to uniform distribution is obtained. As a consequence, the distribution of r-grams on the highest level sequence is shown to be asymptotically uniform with respect to the degree of f (x).