【作者】 朱宣勇；

【导师】 戚文峰；

【作者基本信息】 中国人民解放军信息工程大学 ， 密码学， 2004， 博士

【摘要】 设p是奇素数,整数e≥2,Z/（p^e）是整数模p^e的剩余类环。环Z/（p^e）上序列（?）有如下唯一的p-adic分解:（?）=（?）₀+（?）₁·p+…+（?）_e-1·p^e-1,其中（?）是{0,1,…,p-1}上序列,称（?）是序列（?）的第i权位序列,（?）_e-1是（?）的最高权位序列,它们可自然视为素域GF（p）上序列。 设f（x）是Z/（p^e）上n次本原多项式,它是Z/（p^e）上周期为p^e-1·（pⁿ-1）的首一多项式,并且f（0）≠0（mod p）。设h（x）是{0,1,…,p-1)上多项式,degh（x）<n,使得 x^{pe-2（pn-1）}-1=p^e-1·h（x）（mod f（x）,p^e）。 记Z/（p^e）上所有由f（x）生成的线性递归序列之全体为G（f（x）,p^e）。我们证明了,G（f（x）,p^e）中本原序列最高权位在某些固定的位置上的0元素分布是唯一的。即,任给（?）=（a（t））_t≥0,（?）=（b（t））_t≥0∈G（f（x）,p^e）,（?）≠（?）（mod p）,记（?）=h（x）（?）₀（mod p）,若对使得α（t）≠0的非负整数t,都有a_e-1（t）=0当且仅当b_e-1（t）=0,则（?）=（?）。这一结论说明序列（?）_e-1在α（t）≠0的位置上的0元素分布情形包含序列（?）∈G（f（x）,p^e）的所有信息。称这一特性为Z/（p^e）上本原序列的局部0保熵。它的意义主要表现为:一方面,它更为精确地描述了最高权位序列保熵的具体含义,进一步揭示了本原序列蕴涵信息的分布规律;另一方面,对于Z/（p^e）上本原序列一般保熵函数的研究,它可以提供了一个有力工具。同时,对于Z/（2^e）上本原序列,本文也得到了类似的结论。 基于Z/（p^e）上本原序列的局部0保熵的结果,本文证明了形如φ_e-1(x₀,x₁,…,x_e-1)=x_e-1^k+η_e-2(x₀,x₁,…,x_e-2),2≤k≤p-1,的压缩函数是保熵的,其中η_e-2是素域GF（p）上任意一个e-1元多项式。即,任给（?）,（?）∈G（f（x）,p^e）,若（?）≠（?）（mod p）,则（?）=（?）当且仅当φ_e-1(（?）₀,（?）₁,…,（?）_e-1)=φ_e-1(（?）₀,_?1,…,（?）_e-1)。进一步,若f（x）是Z/（p^e）上强本原多项式,上述形式的不同压缩函数和不同的本原序列对于导出序列的影响都是不同的。这一特性对于Z/（2^e）上本原序列的压缩函数是很难成立的。 FCSR序列中的极大周期序列（简称为l-序列）是一类性质优良的伪随机序列。由FCSR序列的代数表示,可知l-序列是Z/（p^e）上一次本原序列的mod 2导出序列,其中p是奇素数,2是mod p^e的一个本原元。设（?）是Z/（p^e）上n次本原序列,mod 2压缩序列更多还原

【Abstract】 Let p be an odd prime, integer e ≥ 2, and Z/（p^e） be the integer residue ring modulo p^e. Any sequence -|a over Z/（p^e） has an unique /?-adic expansion: -|a = -|a0 + -|a1p +...+ -|a_e-p^e-1, where each -|a_i is a sequence over {0, l,...,p-l}, i = 0, 1,..., e-1. The sequence -|a_i is called i-th level sequence of -|a, and -|a_e-1 the highest-level sequence of -|a. They can be naturally considered as the sequences over the prime field GF（p）.Let f{x) be a primitive polynomial of degree n over Z/（p^e）, which is a monic polynomial of period p^e-1 （pⁿ-1）, such that f（0）≠0 （mod p）. Let h（x） be a polynomial over {0, l,...,p-1}, degh（x） < n, such thatDenoted by G（f（x）, p^e）, the set of all linear recurring sequences generated by f（x） over Z/（p^e）. We prove that, the distribution of zeros on some fixed positions of the highest-level sequence of any primitive sequence in G（f（x）, p^e） is unique. That is, for -|a= （a（t））,t≥0 b = （b（t））t≥0∈G（f{x）,p^e) such that -|a ≠0 （mod p）, we set -|a = h（x）-|a0 （mod p）. If a_e-1 （f） = 0 iff b_e-1 （t） = 0 for any integer t with a（t） ≠0, then -|a = -|b. This implies that the distribution of zeros of -|a_e-1 on the positions t with a（t）≠ 0, contains all information of -|a∈G（f（x）,p^e）. This property is called zero-entropy-preservation of primitive sequences over Z/（p^e）, which can disclose the distribution law of information contained in primitive sequences over Z/（pe）. On the other hand, it can provide a powerful tool for the discussion of the injectivity of a general function acting on primitive sequences over Zl{pe). We also prove that the similar result over Z/（2^e） holds.Based on the result of zero-entropy-preservation of the primitive sequence over Z/（pe）; we prove that the compressing function of form（pe-i（x0;xu-..;xe-i） = 4_i + rje-2（xo;xh...;xe₂）; 2 < k<p-\;is injective; where rje-2 is an arbitrary polynomial function of e-\ variables over the prime field GF（p）. That is; for a; beG（f（x）;pe）; if fl*0 （mod/?）; then a = b iff （pe-\（ao; a\;...; ae-\） = <Pe-i（bo; b\;...; be-\）. Furthermore; we prove that the influence of any injective compressing function of the form above acting on any primitive sequence in G{f[x）; //） is unique. But similar result over Z/（2e） hardly holds.The maximal length FCSR sequences （/-sequences） are thought to be a resource of ideal pseudorandom sequences. From the algebraic representation of FCSR sequence; we can find that; in fact; /-sequence is simply the compression sequence by acting the operation of mod 2 on a primitive sequence of degree 1 over Z/（pe）; where p is an odd prime and 2 is a primitive root modulo/?6. Thus the compressed sequence a （mod 2） can be considered as a natural extension of /-sequence if a is a primitive sequence of degree n over Z/（pe）. In this paper; we prove that the compressed sequence a （mod 2） inherits all information of the original sequence qeG（J{x）; pe). Furthermore; we prove that almost all the modulo operations on primitive sequences over Z/（pe） are injective.The operation of modulo M on primitive sequences over Z/（2e） is also injective; where M is an odd number.LetJ{x) be a primitive polynomial over Z/（2e）; then the highest-level sequence ae-\ contains all information of the original sequence aeG（J（x）; 2e）. In this paper; we discuss that how many bits of ae_i are required to recover the original sequence aeG（J（x）; 2e）. This exact number is called the entropy of the primitive sequence over Z/（2e）; and denote by Eifix); 2e). In this paper; we prove that E（f（x）; 2e） is equivalent to the whole nonlinear complexity; NC（f（x）; 2e）; of all highest-level sequences of the sequences in G（f（x）; 2e）. The whole nonlinear complexity NC（f（x）; 2e） is much smaller than the whole linear complexity of all highest-level sequences. Let/（x） be a primitive polynomial over Z/（22）. If/（.x）（mod 2） is a primitive trinomial over Z/（2）; then NC（J（x）; 2 ） < An. This upper bound is tight.The highest-level sequence Og-\ can uniquely determine the original sequence ae G（f（x）;2e）. In this paper; we propose an algorithm which can recover aeG（f（x）;2e） from ae-\ or a part of Qg-\. This algorithm needs only the least bits of flg-i.更多还原