Finding linearly generated subsequences

We develop a new algorithm to compute determinants of all possible Hankel matrices made up from a given finite length sequence over a finite field. Our algorithm fits within the dynamic programming paradigm by exploiting new recursive relations on the determinants of Hankel matrices together with new observations concerning the distribution of zero determinants among the possible matrix sizes allowed by the length of the original sequence. The algorithm can be used to isolate \emph{very} efficiently linear shift feedback registers hidden in strings with random prefix and random postfix for instance and, therefore, recovering the shortest generating vector. We compare our results empirically with the trivial algorithm which consists of computing determinants for each possible Hankel matrices made up from a given finite length sequence. For instance for sequences of length $4096$, our algorithm is about $83$ times faster than the trivial algorithm on typical worst-case sequences and about $5947$ times faster on easy cases.