Paper 2010/497

Number formula and degree level of ergodic polynomial functions over $\mathbb{Z}$/$2^n\mathbb{Z}$ and generalized result of linear equation on ergodic power-series T-Function

Tao Shi and Dongdai Lin

Abstract

Jin-Song Wang and Wen-Feng Qi gived the sufficient and necessary condition that a polynomial function $f(x)=c_0+c_{1}x+c_2{x}^2+\cdots +c_m{x}^m$ with integer coefficients modulo $2^n(n\ge 3)$ is a single cycle T-function, That is, $f(x)$ generates a single cycle if and only if $c_0$, $c_1$ are odd, ${\mathrm{△}}_1,{\mathrm{△}}_2$ are even, ${\mathrm{△}}_1+{\mathrm{△}}_2+2c_{1,1}\equiv 0\text{func}mod4$, and ${\mathrm{△}}_1+2c_{2,0}+2c_{1,1}\equiv 0\text{func}mod4$, where ${\mathrm{△}}_1=(c_2+c_4+\cdots ),{\mathrm{△}}_2=(c_3+c_5+\cdots )$. A Linear Equation over the coordinate sequences of sequence $$generated by iterated the polynomial single cycle T-function, that is,% \begin{equation} x_{i+2^{j-1},j}=x_{i,j}+x_{i,j-1}+ajA_{i,2}+a(j-1)+b\func{mod}2,3\leq j\leq n-1 \label{equ.1} \end{equation}% given $$, where $$, $$be the j-th bit of $$. $$ is a sequence of period $$ and a, b are constants determined by the coefficients $$. In this paper, using Anashin's general theory, some detail combinatorial result of stirling numbers and Larin's result , we can give the counting formula for the given degree polynomial ergodic(single cycle) T-function. Then, for fixed $$, we can know, what's the least degree $$ that all the single-cycle polynomial transformations can be expressed as the polynomials that degree does not exceed $$ over $$. we deduce that Jin-Song Wang and Wen-Feng Qi's result is a special case of ours, and their linear relation on the coordinate sequences generated by single cycle polynomial T-function can be extended to a more general function class. The equation shows that the sequences generated by these T-functions have potential secure problems.(Thanks for professor Anashin's hint for the motivation of this paper)

Note: Thanks for professor Anashin's hint for the motivation of this paper