论文标题
查找线性生成的子序列
Finding linearly generated subsequences
论文作者
论文摘要
我们开发了一种新算法来计算由有限场上给定的有限长度序列组成的所有可能的Hankel矩阵的决定因素。我们的算法通过在Hankel矩阵的决定因素上利用新的递归关系以及有关原始序列长度允许的可能的矩阵大小之间的零决定因素的分布，将新的递归关系与原始序列的长度允许。该算法可用于隔离\ emph {非常有效的线性移位反馈寄存器，例如随机前缀和随机后缀的字符串中，并因此恢复了最短的生成向量。我们的新数学身份也可以在涉及汉克尔矩阵决定因素的任何其他情况下使用。我们还实现了算法的并行版本。我们将结果与琐碎算法进行比较，该算法包括计算由给定有限长度序列组成的每个可能的Hankel矩阵的决定因素。例如，我们在单个处理器上的新加速方法要比160个处理器上的琐事算法快于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.
