Investigating results and performance of search and construction algorithms for word-based LFSRs, σ-LFSRs

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ-LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ-LFSRs. The search algorithm first constructs the σ-polynomial and then checks the primitiveness of the σ-polynomial, whereas the construction algorithm for the σ-LFSR, first finds a primitive polynomial f(x) and then constructs the primitive σ-LFSR from f(x). In this paper, we present some novel results pertaining to the search algorithm for primitive σ-LFSR along with the exhaustive search space complexity of the search algorithm for σ-LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ-LFSR. Finally, the number of σ-LFSRs similar to the σ-LFSRs generated by the construction algorithm is provided.