Pseudorandom Generators

The recognition of recurrent sequences generated by conservative functions

O. E. Sergeeva

Tomsk State University, Tomsk

Abstract: Let $K$ be a class of functions $f\colon R^n\to R$, where $n=1,2,\dots$. Suppose that $S(K,N)$ is the set of all $N$-prefixes of recurrent sequences generated by functions from $K$. The recognition problem for the property "$x\in S(K,N)$", where $x\in R^N$ and $K$ is the class of conservative functions over the ring $R=\mathbb Z_{p^m}$, is considered. For solving this problem, an algorithm of complexity $\mathrm O(N\log^2N)$ is offered.

Keywords: conservative function, recurrent sequences, circuit of functional elements.

UDC: 511.172+510.52