| Let p be an odd prime, integer e ≥ 2, and Z/(pe) be the integer residue ring modulo pe. Any sequence -|a over Z/(pe) has an unique /?-adic expansion: -|a = -|a0 + -|a1p +...+ -|ae-pe-1, where each -|ai is a sequence over {0, l,...,p-l}, i = 0, 1,..., e-1. The sequence -|ai is called i-th level sequence of -|a, and -|ae-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/(pe), which is a monic polynomial of period pe-1 (pn-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), pe), the set of all linear recurring sequences generated by f(x) over Z/(pe). We prove that, the distribution of zeros on some fixed positions of the highest-level sequence of any primitive sequence in G(f(x), pe) is unique. That is, for -|a= (a(t)),t≥0 b = (b(t))t≥0∈G(f{x),pe) such that -|a ≠0 (mod p), we set -|a = h(x)-|a0 (mod p). If ae-1 (f) = 0 iff be-1 (t) = 0 for any integer t with a(t) ≠0, then -|a = -|b. This implies that the distribution of zeros of -|ae-1 on the positions t with a(t)≠0, contains all information of -|a∈G(f(x),pe). This property is called zero-entropy-preservation of primitive sequences over Z/(pe), 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/(2e) 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) = 4i + rje-2(xo;xh...;xe2); 2 < ki 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.
|
PDF Full Text Request