  We investigate the bit-search type irregular decimation algorithms that are
used within LFSR-based stream ciphers. In particular, we concentrate on BSG and
ABSG, and consider two different setups for the analysis. In the first case,
the input is assumed to be a m-sequence; we show that all possible output
sequences can be classified into two sets, each of which is characterized by
the equivalence of their elements up to shifts. Furthermore, we prove that the
cardinality of each of these sets is equal to the period of one of its elements
and subsequently derive the first known bounds on the expected output period
(assuming that no subperiods exist). In the second setup, we work in a
probabilistic framework and assume that the input sequence is evenly
distributed (i.e., independent identically distributed Bernoulli process with
probability 1/2). Under these assumptions, we derive closed-form expressions
for the distribution of the output length and the output rate, which is shown
to be asymptotically Gaussian-distributed and concentrated around the mean with
exponential tightness.
