Searching for nonlinear feedback shift registers with parallel computing

• The numerical verification of conjecture of Chan et al. (FSEʼ94) up to order n=29n=29.
• Enumeration of all one term quadratic m  -sequences up to order n=21n=21.
• Finding new NLFSRs generating modified de Bruijn sequences up to order n=31n=31.
• Application of parallel computing to the above search problems.
• Calculations of linear complexities of the found sequences up to order n=26n=26.

Nonlinear feedback shift registers (NLFSRs) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of linear feedback shift registers (LFSRs). In general, it is not known how to construct all NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. Advanced technology of parallel computing has been applied both in software and hardware to search for maximum period NLFSRs having a fairly simple algebraic normal form.