American Institute of Mathematical Sciences

Advanced
May  2020, 14(2): 307-318. doi: 10.3934/amc.2020022

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

Received  July 2018 Revised  April 2019 Published  May 2020 Early access  September 2019

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: Pseudorandom sequence, expansion complexity, linear complexity, Gröbner basis, inversive generator.
Mathematics Subject Classification: Primary: 11T71, 11Y16, 94A60, 94A55, 68Q25.
Citation: Domingo Gómez-Pérez, László Mérai. Algebraic dependence in generating functions and expansion complexity. Advances in Mathematics of Communications, 2020, 14 (2) : 307-318. doi: 10.3934/amc.2020022
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.  Google Scholar

[2]

L. Carlitz, The distribution of irreducible polynomials in several indeterminates, Illinois Journal of Mathematics, 7 (1963), 371-375.  doi: 10.1215/ijm/1255644947.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[7]

D. M. Goldschmidt, Algebraic Functions and Projective Curves, Graduate Texts in Mathematics, 215. Springer-Verlag, New York, 2003. doi: 10.1007/b97844.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge, 2013.  doi: 10.1017/CBO9781139856065.  Google Scholar

show all references

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.  Google Scholar

[2]

L. Carlitz, The distribution of irreducible polynomials in several indeterminates, Illinois Journal of Mathematics, 7 (1963), 371-375.  doi: 10.1215/ijm/1255644947.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[7]

D. M. Goldschmidt, Algebraic Functions and Projective Curves, Graduate Texts in Mathematics, 215. Springer-Verlag, New York, 2003. doi: 10.1007/b97844.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge, 2013.  doi: 10.1017/CBO9781139856065.  Google Scholar
[1]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[2]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[3]

Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & Continuous Dynamical Systems, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115
[4]

Arnulf Jentzen, Felix Lindner, Primož Pušnik. On the Alekseev-Gröbner formula in Banach spaces. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 4475-4511. doi: 10.3934/dcdsb.2019128
[5]

Ismara  Álvarez-Barrientos, Mijail Borges-Quintana, Miguel Angel Borges-Trenard, Daniel Panario. Computing Gröbner bases associated with lattices. Advances in Mathematics of Communications, 2016, 10 (4) : 851-860. doi: 10.3934/amc.2016045
[6]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334
[7]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477
[8]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299
[9]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[10]

Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[11]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[12]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[13]

Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019
[14]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385
[15]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046
[16]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[17]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[18]

Roland Zweimüller. Asymptotic orbit complexity of infinite measure preserving transformations. Discrete & Continuous Dynamical Systems, 2006, 15 (1) : 353-366. doi: 10.3934/dcds.2006.15.353
[19]

Erik M. Bollt, Joseph D. Skufca, Stephen J . McGregor. Control entropy: A complexity measure for nonstationary signals. Mathematical Biosciences & Engineering, 2009, 6 (1) : 1-25. doi: 10.3934/mbe.2009.6.1
[20]

Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (162)
  • HTML views (427)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences