On nonlinear feedback shift registers with short periods

Motivated by certain cryptological problems, some specific properties of two classes of feedback shift registers with short periods are discussed in this paper.     

The adjacency graphs of some feedback shift registers

In this paper, we consider the adjacency graphs of some feedback shift registers (FSRs), namely, the FSRs with characteristic functions of the form \(g=(x_0+x_1)*f\). Firstly, we give some properties about these FSRs. We prove that these FSRs generate only prime cycles, and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. For example, it is shown that, when f contains an odd number of terms, the adjacency graph of \({\mathrm {FSR}}((x_0+x_1)*f)\) can be determined directly from the adjacency graph of \({\mathrm {FSR}}(f)\). Then, as an application of these results, we continue the work of Li et al. (IEEE Trans Inf Theory 60(5):3052–3061, 2014) to determine the adjacency graphs of \({\mathrm {FSR}}((1+x)^4p(x))\) and \({\mathrm {FSR}}((1+x)^5p(x))\), where p(x) is a primitive polynomial, and construct a large class of De Bruijn sequences from them.     

On the cycle structure of certain classes of nonlinear shift registers

When m = qt, g(x_t+1, x_2t+1,…, x_(q?1)t+1) is a linear combination of only odd (or only even) elementary symmetric functions, then every cycle of the nonlinear shift register with feedback function f(x₁, x₂,…, x_m) = x₁ + g(x_t+1, x_2t+1,…, x_(q?1)t+1) has a minimal period dividing m(q+1). It is also shown that when g is derived from a cyclic code with minimum distance ?3, every cycle of this shift register has a minimal period dividing m(q + 1).     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).     

On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions

We show that all sequences generated by a set of nonlinear shift registers with symmetric feedback functions have minimal periods dividing n(n + 1). Here n is the number of shift register stages.     

On the number of irreducible linear transformation shift registers

We deal with the problem of counting the number of irreducible linear transformation shift registers (TSRs) over a finite field. In a recent paper, Ram reduced this problem to calculate the cardinality of some set of irreducible polynomials and got explicit formulae for the number of irreducible TSRs of order two. We find a bijection between Ram’s set to another set of irreducible polynomials which is easier to count, and then give a conjecture about the number of irreducible TSRs of any order. We also get explicit formulae for the number of irreducible TSRs of order three.     

Primitive polynomials,singer cycles and word-oriented linear feedback shift registers

Using the structure of Singer cycles in general linear groups, we prove that a conjecture of Zeng et al. (Word-Oriented Feedback Shift Register: σ-LFSR, 2007) holds in the affirmative in a special case, and outline a plausible approach to prove it in the general case. This conjecture is about the number of primitive σ-LFSRs of a given order over a finite field, and it generalizes a known formula for the number of primitive LFSRs, which, in turn, is the number of primitive polynomials of a given degree over a finite field. Moreover, this conjecture is intimately related to an open question of Niederreiter (Finite Fields Appl 1:3–30, 1995) on the enumeration of splitting subspaces of a given dimension.     

Zero distribution of some shift polynomials

Given an entire function f of finite order ρ, let $g(f):={\sum }_{j=1}^k{b}_j(z)f(z+c_j)$ be a shift polynomial of f with small meromorphic coefficients $b_j$ in the sense of $O(r^{\lambda +\epsilon })+S(r,f)$, $\lambda <\rho$. Provided α, β, $b_0$ are similar small meromorphic functions, we consider zero distribution of $f^n{(g(f))}^s?b_0$, resp. of $g(f)?\alpha f^n?\beta$.     

An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).     

Singular perturbations of some nonlinear problems

We deal with singular perturbations of nonlinear problems depending on a small parameter ε > 0. First we consider the abstract theory of singular perturbations of variational inequalities involving some nonlinear operators, defined in Banach spaces, and describe the asymptotic behavior of these solutions as ε → 0. Then these abstract results are applied to some boundary value problems. Bibliography: 15 titles.     

Oscillation of some nonlinear difference equations

We investigate the oscillatory behavior of all solutions of a new class of first order nonlinear neutral difference equations. Several explicit oscillation criteria are established. Our main results are supported by illustrative examples.     

Newton-Kantorovich approximations to nonlinear singular integral equation with shift

The paper is concerned with the applicability of some new conditions for the convergence of Newton-kantorovich approximations to solution of nonlinear singular integral equation with shift of Uryson type. The results are illustrated in generalized Holder space.     

Analyticity of solutions of some nonlinear equations

Siberian Mathematical Journal -     

Oscillations in some nonlinear economic relationships

In this paper we consider a simple family of nonlinear dynamical systems generated by smooth functions. Some theorems for the existence and the uniqueness of the limit cycles of the systems are presented. If f and g are generating functions with unique limit cycles and xf(x) < xg(x), for all x ≠ 0, then according to the ‘bounding theorem’ proved in the paper, the limit cycle of the system generated by f is bounded by the limit cycle of the system generated by g. This gives us a method to estimate the amplitude of the oscillations also for systems for which we do not know the generating function exactly. As an application we extend the nonlinear business cycle model proposed by Tönu Puu (1989).