Finding linearly generated subsequences
This provides a faster method for isolating linear shift feedback registers in strings, which is useful in cryptography and coding theory, though it appears incremental as it builds on dynamic programming with new recursive relations.
The paper tackles the problem of efficiently computing determinants of all possible Hankel matrices from a finite sequence over a finite field, with results showing their new algorithm on a single processor outperforms a trivial parallel approach on 160 processors for sequences of length 16384.
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. Our new mathematical identities can be used also in any other situations involving determinants of Hankel matrices. We also implement a parallel version of our algorithm. 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. Our new accelerated approach on a single processor is faster than the trivial algorithm on 160 processors for input sequences of length 16384 for instance.