快速寻找非线性反馈移位寄存器的编程算法

Fast Programming Algorithm to Find Non-Linear Feedback Shift Register

在流密码中,非线性反馈移位寄存器(non-linear feedback shift register,NLFSR)是一种常用的安全性较高的伪随机序列生成器。目前仍然没有一种普遍有效的数学算法,能够根据给定的序列或者序列周期,直接推导出NLFSR。提出了一种快速寻找NLFSR的编程算法。该算法基于统一计算架构(compute unified device architecture,CUDA)和并行计算来实现,计算速度快,尤其适用于处理高次数的复杂NLFSR。并且该算法可以快速大规模地计算出NLFSR,为未来研究寻找NLFSR的数学算法提供了大量的实验数据。

Non-linear feedback shift register （NLFSR） is a common device to generate pseudo-random sequences in stream cipher. However, there is still no effective mathematical algorithm to find NLFSRs for a given period or output sequence. This paper provides a quick method to find NLFSRs. This method is a programming algorithm based on compute unified device architecture （CUDA） and parallel computing, and can quickly find NLFSRs for the given period or output sequence. This method has very good performance on both simple and complex NLFSRs. With this new method, people can easily get a large amount of experimental data about NLFSRs. It will be a great help for the future research on the mathematical algorithm to find NLFSRs.feedback shift register （NLFSR）