American Institute of Mathematical Sciences

Advanced
August  2007, 1(3): 307-319. doi: 10.3934/amc.2007.1.307

The asymptotic behavior of N-adic complexity

Andrew Klapper 1,

1. 

University of Kentucky, 779A F. Paul Anderson Tower, Lexington, KY 40506-0046, United States

Received  December 2006 Revised  July 2007 Published  July 2007

We study the asymptotic behavior of stream cipher security mea- sures associated with classes of sequence generators such as linear feedback shift registers and feedback with carry shift registers. For nonperiodic sequences we consider normalized measures and study the set of accumulation points for a fixed sequence. We see that the set of accumulation points is always a closed subinterval of $[0, 1]$. For binary or ternary FCSRs we see that this interval is of the form $[B, 1-B]$, a result that is an analog of an earlier result by Dai, Jiang, Imamura, and Gong for LFSRs.
Keywords: Sequences, N-adic complexity, shift registers., stream ciphers.
Mathematics Subject Classification: 94A05, 94A55, 94A6.
Citation: Andrew Klapper. The asymptotic behavior of N-adic complexity. Advances in Mathematics of Communications, 2007, 1 (3) : 307-319. doi: 10.3934/amc.2007.1.307
[1]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209
[2]

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

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

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[5]

Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015
[6]

Valentin Afraimovich, Lev Glebsky. Measures related to $(\epsilon,n)$-complexity functions. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 23-34. doi: 10.3934/dcds.2008.22.23
[7]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191
[8]

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

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

Sarah Bailey Frick. Limited scope adic transformations. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 269-285. doi: 10.3934/dcdss.2009.2.269
[11]

Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030
[12]

Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016
[13]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015
[14]

Frédéric Bernicot, Bertrand Maury, Delphine Salort. A 2-adic approach of the human respiratory tree. Networks & Heterogeneous Media, 2010, 5 (3) : 405-422. doi: 10.3934/nhm.2010.5.405
[15]

Daniel Gonçalves, Marcelo Sobottka. Continuous shift commuting maps between ultragraph shift spaces. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 1033-1048. doi: 10.3934/dcds.2019043
[16]

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

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

Michael Schraudner. Projectional entropy and the electrical wire shift. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 333-346. doi: 10.3934/dcds.2010.26.333
[19]

Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036
[20]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences