The complexity of initial state recovery for a class of filter generators. (Russian. English summary) Zbl 1475.94040

Summary: A recovery problem for the initial state of the \(m\)-th order recurrent sequence from the output values of filter function \(F\). Under natural conditions on the feedback function \(f\) and filter function \(F\) the complexity of initial state recovery from linear (in \(m\)) number of output values is shown to be linear in \(m\). Coefficients of these linear functions are defined by the cardinalities of alphabet of output values, alphabet of input sequence elements and numbers of essential arguments of functions \(f\) and \(F\).


94A12 Signal theory (characterization, reconstruction, filtering, etc.)
11B37 Recurrences
Full Text: DOI MNR


[1] Shnaier B., Prikladnaya kriptografiya. Protokoly, algoritmy, iskhodnye teksty na yazyke SI, TRIUMF, M., 2003
[2] Malyshev F. M., “Porozhdayuschie nabory elementov rekurrentnykh posledovatelnostei”, Trudy po diskretnoi matematike, 11, no. 2, 2008, 86-111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.