2019/05/03 by Gómez-Pérez, Domingo, Mérai, László
#FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1905.01079
In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. Recently, a series of paper has been published for analysis of expansion complexity and for testing sequences in terms of this new measure of randomness. In this paper, we continue this analysis. First we study the expansion complexity in terms of the Gröbner basis of the underlying polynomial ideal. Next, we prove bounds on the expansion complexity for random sequences. Finally, we study the expansion complexity of sequences defined by differential equations, including the inversive generator.