On obtaining long m-sequences from low-degree primitive polynomials
Dimitri Kagaris · Discrete Applied Mathematics · 2025
Maximum-length sequences of length 2 n − 1 (m-sequences) are typically obtained by starting from a primitive polynomial of degree n over G F ( 2 ) and configuring a Linear Feedback Shift Register (LFSR) based on that polynomial. In this study, we investigate the generation of long m-sequences based on a primitive polynomial of low degree. Specifically, we investigate a very simple form of an LFSR structure, referred to as Two-Multiplier Split LFSR (2M-SLFSR) , that consists of m δ -bit cells and is based on a single low-degree primitive polynomial of degree δ ≥ 2 over G F ( 2 ) and which can generate, with proper configuration, an m-sequence of length 2 m δ − 1 . For example, we show that starting from the primitive polynomial x 2 + x + 1 over G F ( 2 ) , a 2M-SLFSR with m = 599 2-bit cells can be constructed that yields an m-sequence of length 2 1198 − 1 . M-sequences of large length such as 2 512 − 1 obtained from low degree primitive polynomials via LFSR structures akin to 2M-SLFSR find current applications in stream ciphers like those used in SNOW-V and SNOW-Vi.