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\geq 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, $\triangle _{1},\triangle _{2}$ are even, $% \triangle _{1}+\triangle _{2}+2c_{1,1}\equiv 0\func{mod}4$, and $\triangle _{1}+2c_{2,0}+2c_{1,1}\equiv 0\func{mod}4$, where $\triangle _{1}=(c_{2}+c_{4}+\cdots ),\triangle _{2}=(c_{3}+c_{5}+\cdots )$. A Linear Equation over the coordinate sequences of sequence $\{x_{i}\}$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 $x_{0}\in \mathbb{Z}/2^{n}\mathbb{Z}$, where $x_{i}=f(x_{i-1})\func{mod% }2^{n}$, $x_{i,j}$be the j-th bit of $x_{i}$. $A_{i,2}$ is a sequence of period $4$ and a, b are constants determined by the coefficients $c_{i}$. 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 $n$, we can know, what's the least degree $m$ that all the single-cycle polynomial transformations can be expressed as the polynomials that degree does not exceed $m$ over $% \mathbb{Z}/2^{n}\mathbb{Z}$. 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