Algebraic dependence in generating functions and expansion complexity

Domingo Gómez-Pérez; László Mérai

doi:10.3934/amc.2020022

Article Contents

2020, Volume 14, Issue 2: 307-318. Doi: 10.3934/amc.2020022

This issue Previous Article Dual-Ouroboros: An improvement of the McNie scheme Next Article Quaternary group ring codes: Ranks, kernels and self-dual codes

Algebraic dependence in generating functions and expansion complexity

Domingo Gómez-Pérez^1, and
László Mérai^2, ,

1.
Department of Mathematics, University of Cantabria, Santander 39005, Spain
2.
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Straße 69, A-4040 Linz, Austria

^* Corresponding author: László Mérai
^* Corresponding author: László Mérai

Received: July 2018

Revised: April 2019

Early access: September 2019

Published: May 2020

Abstract Full Text(HTML) Related Papers Cited by

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ö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.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 11Y16, 94A60, 94A55, 68Q25.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	S. Balasuriya, I. E. Shparlinski and A. Winterhof, An average bound for character sums with some counter-dependent recurrence sequences, Rocky Mountain J. Math., 39 (2009), 1403-1409. doi: 10.1216/RMJ-2009-39-5-1403.
[2]	L. Carlitz, The distribution of irreducible polynomials in several indeterminates, Illinois Journal of Mathematics, 7 (1963), 371-375. doi: 10.1215/ijm/1255644947.
[3]	C. Diem, On the use of expansion series for stream ciphers, LMS Journal of Computation and Mathematics, 15 (2012), 326-340. doi: 10.1112/S146115701200109X.
[4]	D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, Graduate Texts in Mathematics, 150. Springer-Verlag, New York, 1995. doi: 10.1007/978-1-4612-5350-1.
[5]	E. D. El-Mahassni and A. Winterhof, On the distribution and linear complexity of counter-dependent nonlinear congruential pseudorandom number generators, JP J. Algebra Number Theory Appl., 6 (2006), 411-423.
[6]	J. C. Faugére, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, 16 (1993), 329-344. doi: 10.1006/jsco.1993.1051.
[7]	D. M. Goldschmidt, Algebraic Functions and Projective Curves, Graduate Texts in Mathematics, 215. Springer-Verlag, New York, 2003. doi: 10.1007/b97844.
[8]	D. Gomez, Multiplicative character sums with counter-dependent nonlinear congruential pseudorandom number generators, in Sequences and Their Applications—SETA 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6338 (2010), 188–195. doi: 10.1007/978-3-642-15874-2_15.
[9]	D. Gómez-Pérez, L. Mérai and H. Niederreiter, On the expansion complexity of sequences over finite fields, IEEE Trans. Inform. Theory, 64 (2018), 4228-4232. doi: 10.1109/TIT.2018.2792490.
[10]	L. Mérai, H. Niederreiter and A. Winterhof, Expansion complexity and linear complexity of sequences over finite fields, Cryptography and Communications, 9 (2017), 501-509. doi: 10.1007/s12095-016-0189-2.
[11]	A. Shamir and B. Tsaban, Guaranteeing the diversity of number generators, Inform. and Comput., 171 (2001), 350-363. doi: 10.1006/inco.2001.3045.
[12]	I. E. Shparlinski and A. Winterhof, On the discrepancy and linear complexity of some counter-dependent recurrence sequences, in Sequences and Their Applications—SETA 2006, Lecture Notes in Comput. Sci., Springer, Berlin, 4086 (2006), 295–303. doi: 10.1007/11863854_25.
[13]	J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge, 2013. doi: 10.1017/CBO9781139856065.