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

expansion complexityGröbner basisinversive generatorlinear complexitypseudorandom sequence

Mathematics Subject Classification ID

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

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.

Review text

\textit{C. Diem} [Algebra Number Theory 7, No. 6, 1281--1323 (2013; Zbl 1300.11132)] introduced a measure of pseudorandomness for cryptographic sequences called expansion complexity which was further analyzed by the second author et al. [Cryptogr. Commun. 9, No. 4, 501--509 (2017; Zbl 1409.94855)] and the authors et al. [IEEE Trans. Inf. Theory 64, No. 6, 4228--4232 (2018; Zbl 1395.94262)]. First the authors express the expansion complexity in terms of the Gröbner basis of its defining ideal. Then they present a corrected form of [the second author et al., loc. cit., Theorem 4] on the typical value of the expansion complexity. Finally, they study the expansion complexity of sequences defined by differential equations including the explicit 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

• 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
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 5174819 (Why is no real title available?)
• 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

(4)

• Pseudorandom sequences derived from automatic sequences
• Complexity analysis of a top down algorithm motivated by power product expansions
• Expansion complexity and linear complexity of sequences over finite fields
• On the Nth 2-adic complexity of binary sequences identified with algebraic 2-adic integers

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)