## 5 Efficiency and Security  
The implementation presented in Section 3 considerably reduces the execution time of the LFSRs defined in \(GF(2^{n})\). Specifically, an implementation of the LFSR used in the SNOW 3G stream cipher has been performed and compared with the implementation provided in the technical specification of the protocol [10]. This is an LFSR \(<16,f(x),32>\). Hence, the equivalent model is based on 32 LFSRs \(<512,p(x)>\). The polynomial \(p(x)\) is built from 1024 elements generated using the official implementation [10] following the steps established in Algorithm 1. The result is that the 32 decimated sequences have the same minimal polynomial \(p(x)\) of degree 512, whose coefficients are represented below in compact hexadecimal format:  
\[84009\text{C624D4F75F17 EDA41C663C5 DFDED8A535 DA1C5F70824152A7} \tag{20}\] \[\text{C23}EDB90D572852A765 FF5F2012A64F5D3 FD361B005 ADBA45A1995\] (21) \[\text{E64E48362706D62606828} \tag{22}\]  
Despite the fact that \(p(x)\) has 250 non-zero coefficients, and therefore 250 XOR operations are required to generate the next element in the sequence, the execution time is 3.3 times lower than the original implementation. The computation of the matrices \(A^{(i)}\) is not considered, since this is performed prior to the normal operating of the LFSR. The times have been calculated by taking the average of 10 repetitions of each generation of 1000, 10,000, 20,000, 50,000, and 100,000 elements. Both implementations have been made in Python 3.9 language and have been executed on an Intel(R) Core(TM) i7-10510U 64-bit processor with 16 GB of RAM. Although the SNOW 3G algorithm has been designed to be executed on 32-bit platforms, the tests carried out on a 64-bit processor are completely valid since the greater word length of the processor compared to the algorithm does not affect the normal execution of our implementation. Note that the goal is to achieve an implementation of an algorithm defined in \(GF(2^{n})\) using \(n\)-bit operations. The case of working with processors of more than \(n\) bits offers the possibility of developing new faster implementations to make the most of their capacity, but requires adapting the algorithms to the new processor architecture. This is outside the scope of this work. As mentioned in the Section 3, the net bit generation rate is increased by \(n\) when compared to a single binary LFSR implementation, that is, to a binary LFSR using the same connection polynomial. However, the improvement observed in the tests on SNOW 3 Gdoes not reach the net rate. This is mainly due to the number of non-zero coefficients in \(p(x)\) that slow down the computation. Therefore, in the case of equivalent binary polynomials \(p(x)\) with a few nonzero coefficients, the real rate will reach the net rate. In the general case, the fewer non-zero coefficients in \(p(x)\), the greater the improvement to the generation rate. The efficiency of the proposed implementations, shown in Section 3 affects the security of the cryptosystems used by these LFSRs, although, in general, they are not intended to replace those currently used by most devices, such as smartphones, but rather for use in mobile devices without any type of restriction, such as personal computers or servers. Using the equivalent model implies multiplying by \(n\), the number of bits needed to generate a new element of the \(m\)-sequence over \(GF(2^{n})\), that is, to generate \(n\) bits. In the case of SNOW 3G, it goes from 512 to 16,384 bits. Therefore, the theoretical improvement of the execution time by a factor \(n\) is associated with an increase in the same factor \(n\) in the amount of memory needed to generate the same number of bits. As a consequence, this implementation provides a substantial improvement for the calculation of \(m\)-sequences that, although it could not be deployed on some devices, could always be used for cryptanalysis tasks. Regarding the cost of our proposal, an increment in the memory cells must be taken in mind, rising from \(nL\) to \(n^{2}L\) bits.