**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)

**Category / Keywords: **foundations / T-function, ergodic polynomial {\small \ }over $\mathbb{Z}$/$2^{n}\mathbb{Z}${\small \ }, ergodic power-series

**Date: **received 26 Sep 2010, withdrawn 12 Oct 2010

**Contact author: **shitao at is iscas ac cn

**Available format(s): **(-- withdrawn --)

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

**Version: **20101012:155333 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]