Algebraic dependence in generating functions and expansion complexity

DOI10.3934/AMC.2020022MaRDI QIDQ2176295zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

linear complexitypseudorandom sequenceexpansion complexityinversive generatorGröbner basis

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)

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.

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

Cites work

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

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)