###### Abstract  
Many stream ciphers employ linear feedback shift registers (LFSRs) to generate pseudorandom sequences. Many recent LFSRs are defined in \(GF(2^{n})\) to take advantage of the \(n\)-bit processors, instead of using the classic binary field. In this way, the bit generation rate increases at the expense of a higher complexity in computations. For this reason, only certain primitive polynomials in \(GF(2^{n})\) are used as feedback polynomials in real ciphers. In this article, we present an efficient implementation of the LFSRs defined in \(GF(2^{n})\). The efficiency is achieved by using equivalent binary LFSRs in combination with binary \(n\)-bit grouped operations, \(n\) being the processor word's length. This improvement affects the general considerations about the security of cryptographic systems that uses LFSR. The model also allows the development of a faster method to test the primitiveness of polynomials in \(GF(2^{n})\). L SFR; stream cipher; \(m\)-sequence; primitive polynomial; extended Galois field; symmetric encryption 20221099660  
wireless communication systems, e.g., Bluetooth [4], wireless area networks [5], or GSM [6]. On the other hand, although LFSRs are generically defined on a finite field \(GF(q)\), practical implementations of these ciphers are carried out on \(GF(2)\) to integrate with bitwise operations. Nevertheless, these operations are clearly inefficient when using current processors that work with 16-, 32-, or 64-bit words. For this reason, the extended Galois fields \(GF(2^{n})\), where \(2^{n}\) matches the processor word length, have been analyzed to substitute \(GF(2)\) in cryptographic applications [7; 8; 9]. In the particular case of LFSR-based stream ciphers, the SNOW 3G algorithm [10] is currently used in 3G and 4G mobile communication systems, and several proposals have recently appeared to be applied to 5G communications [11; 12; 13]. However, computations on an extended field are time consuming, much more than in the base field [14]. Although the bit generation rate improves \(n\) times the binary case, the overall performance of the system does not, sometimes being even lower. In fact, several methods have been developed to reduce computational time, such as precomputed tables, optimized algorithms for multiplication [15], or the use of representations of the \(GF(2^{n})\) elements in terms of \(GF(2^{m})\) elements with \(m<n\). In contrast to binary case, where any primitive polynomial guarantees a sequence of maximum length, only certain primitive polynomials that facilitate its implementation are used in extended fields. This means that they do not require excessive resource consumption, as the SNOW 3G case does, defined to work on devices with 32-bit processors by combining operations with 32-bit and 8-bit arguments. On the other hand, the identification of primitive polynomials in \(GF(2^{n})\) requires a much higher computational effort than in the binary case. This article presents two methods that reduce the execution time for the implementation of an LFSR and the search for primitive polynomials in the extended filed \(GF(2^{n})\). These methods are based on the model that establishes a direct relationship between the \(m\)-sequence generated by an LFSR in \(GF(2^{n})\) and the interleaving of \(n\)\(m\)-sequences generated by \(n\) LFSRs in \(GF(2)\). This relationship was used by [PERSON] and [PERSON] [16] to build primitive polynomials in \(GF(2^{n})\) in terms of primitive polynomials in \(GF(2)\), establishing the relationships that must hold between both polynomials. We propose to use these relationships in the opposite direction; that is, we propose to represent the primitive polynomial over \(GF(2^{n})\) in terms of binary LFSRs. In this way, the same sequences will be generated using only binary operations (XOR).