An Efficient Algorithm to Compute the Linear Complexity of Binary Sequences

Fúster-Sabater, A.; Requena, V.; Cardell, S.D.
Mathematics 2022, 10, 794

Binary sequences are algebraic structures currently used as security elements in Internet of Things devices, sensor networks, e-commerce, and cryptography. In this work, a contribution to the evaluation of such sequences is introduced. In fact, we present a novel algorithm to compute a fundamental parameter for this kind of structure: the linear complexity, which is related to the predictability (or non-predictability) of the binary sequences. Our algorithm reduced the computation of the linear complexity to just the addition modulo two (XOR logic operation) of distinct terms of the sequence. The performance of this procedure was better than that of other algorithms found in the literature. In addition, the amount of required sequence to perform this computation was more realistic than in the rest of the algorithms analysed. Tables, figures, and numerical results complete the work.


This work was supported in part by the Spanish State Research Agency (AEI) of the Ministry of Science and Innovation (MICINN), Project P2QProMeTe (PID2020-112586RB-I00/AEI/ 10.13039/501100011033), co-funded by the European Regional Development Fund (ERDF, EU). It is also supported by Comunidad de Madrid (Spain) under Project CYNAMON (P2018/TCS-4566), co-funded by FSE and European Union FEDER funds. The work of the second author was partially supported by Spanish Grant VIGROB-287 of the University of Alicante.