Algebraic dependence in generating functions and expansion complexity

DOI10.3934/AMC.2020022zbMATH Open1453.94052arXiv1905.01079OpenAlexW2971669121WikidataQ127243066 ScholiaQ127243066MaRDI QIDQ2176295FDOQ2176295

Authors: Domingo Gómez-Pérez, László Mérai 

Publication date: 4 May 2020

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Abstract: 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"obner 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.

Full work available at URL: https://arxiv.org/abs/1905.01079

Recommendations

• Generative complexity in algebra
• COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
• Asymptotics and algebraicity of some generating functions
• Complexity of short generating functions
• Exponential generating functions and complexity of Lie varieties
• Expansion of generating functions involving various polynomials
• scientific article; zbMATH DE number 17839
• scientific article; zbMATH DE number 976063
• scientific article; zbMATH DE number 3936520
• STACS 2005

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]linear complexitypseudorandom sequenceexpansion complexityinversive generator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Title not available (Why is that?)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Algebraic Functions and Projective Curves
• The distribution of irreducible polynomials in several indeterminates
• On the use of expansion series for stream ciphers
• Expansion complexity and linear complexity of sequences over finite fields
• Guaranteeing the diversity of number generators
• On the Discrepancy and Linear Complexity of Some Counter-Dependent Recurrence Sequences
• An average bound for character sums with some counter-dependent recurrence sequences
• Multiplicative character sums with counter-dependent nonlinear congruential pseudorandom number generators
• Title not available (Why is that?)
• On the Expansion Complexity of Sequences Over Finite Fields

Cited In (3)

• Complexity analysis of a top down algorithm motivated by power product expansions
• Pseudorandom sequences derived from automatic sequences
• Expansion complexity and linear complexity of sequences over finite fields

This page was built for publication: Algebraic dependence in generating functions and expansion complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176295)