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  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]

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

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[3]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[4]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267
[5]

Denis Serre. Non-linear electromagnetism and special relativity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 435-454. doi: 10.3934/dcds.2009.23.435
[6]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[7]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[8]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[9]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[10]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302
[11]

Shumin Li, Masahiro Yamamoto, Bernadette Miara. A Carleman estimate for the linear shallow shell equation and an inverse source problem. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 367-380. doi: 10.3934/dcds.2009.23.367
[12]

Qianqian Hou, Tai-Chia Lin, Zhi-An Wang. On a singularly perturbed semi-linear problem with Robin boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 401-414. doi: 10.3934/dcdsb.2020083
[13]

He Zhang, John Harlim, Xiantao Li. Estimating linear response statistics using orthogonal polynomials: An RKHS formulation. Foundations of Data Science, 2020, 2 (4) : 443-485. doi: 10.3934/fods.2020021
[14]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[15]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[16]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055
[17]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168
[18]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266
[19]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[20]

Jonathan J. Wylie, Robert M. Miura, Huaxiong Huang. Systems of coupled diffusion equations with degenerate nonlinear source terms: Linear stability and traveling waves. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 561-569. doi: 10.3934/dcds.2009.23.561

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (130)
  • HTML views (424)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences