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]

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

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

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

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

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

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

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

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

Lin Yi, Xiangyong Zeng, Zhimin Sun. On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020091
[12]

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

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

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

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

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020334
[17]

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

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

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

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

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences