American Institute of Mathematical Sciences

Advanced
February  2021, 15(1): 155-165. doi: 10.3934/amc.2020050

Some properties of the cycle decomposition of WG-NLFSR

Yujuan Li a, , Huaifu Wang a, , Peipei Zhou b, and  Guoshuang Zhang a,

a. 

Science and Technology on Information Assurance Laboratory, Beijing, China
b. 

Data Communication Science and Technology Research Institute, Beijing, China

Received  December 2018 Revised  September 2019 Published  January 2020

In this paper, we give some properties of the cycle decomposition of a nonlinear feedback shift register called WG-NLFSR which was presented by Mandal and Gong recently. First we give the parity of the state transition transformation of WG-NLFSR and then by the relation of the parity of a permutation and its number of cycles given in Theorem 2 in Section 1, we show that the number of cycles in the cycle decomposition of WG-NLFSR is even. Second we study the properties of the cycle decomposition of WG-NLFSR when the coefficients of the characteristic polynomial belong to the proper subfields of the finite field on which the WG-NLFSR is defined. Finally, we give some properties of the cycle decomposition of the filtering WG7-NLFSR.

Keywords: Permutation, WG-NLFSR, cycle decomposition.
Mathematics Subject Classification: 94A55, 94A60.
Citation: Yujuan Li, Huaifu Wang, Peipei Zhou, Guoshuang Zhang. Some properties of the cycle decomposition of WG-NLFSR. Advances in Mathematics of Communications, 2021, 15 (1) : 155-165. doi: 10.3934/amc.2020050
References:
[1] P. B. Bhattacharya, S. K. Jain and S. R. Nagpaul, Basic Abstract Algebra, 2nd Edition, Cambridge University Press, Cambridge, 1994.  doi: 10.1017/CBO9781139174237.  Google Scholar
[2]

U. Cheng, On the cycle structure of certain classes of nonlinear shift registers, Journal of Combinatorial Theory, 37 (1984), 61-68.  doi: 10.1016/0097-3165(84)90019-0.  Google Scholar

[3]

H. Dobbertin, Kasami power functions, permutation polynomials and cyclic difference sets, Difference Sets, Sequences and Their Correlation Properties (Bad Windsheim, 1998), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 542 (1999), 133-158.   Google Scholar

[4]

S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, Calif.-Cambridge-Amsterdam, 1967.  Google Scholar

[5]

G. Gong and A. M. Youssef, Cryptographic properties of the Welch-Gong transformation sequence generators, IEEE Transactions on Information Theory, 48 (2002), 2837-2846.  doi: 10.1109/TIT.2002.804043.  Google Scholar

[6]

T. Helleseth, Nonlinear shift registers - A survey and challenges, Algebraic Curves and Finite Fields, Radon Ser. Comput. Appl. Math., De Gruyter, Berlin, 16 (2014), 121-144.   Google Scholar

[7]

K. Kjeldsen, On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions, Journal of Combinatorial Theory Ser. A, 20 (1976), 154-169.  doi: 10.1016/0097-3165(76)90013-3.  Google Scholar

[8]

K. Mandal and G. Gong, Filtering nonlinear feedback shift registers using Welch-Gong transformations for securing RFID applications, ICST Trans. Security Safety, 3 (2016), e3.   Google Scholar

[9]

J. Mykkeltveit, M. K. Siu and P. Tong, On the cycle structure of some nonlinear shift register sequences, Information and Control, 43 (1979), 202-215.  doi: 10.1016/S0019-9958(79)90708-3.  Google Scholar

[10] Z. X. Wan and Z. D. Dai, Nonlinear Feedback Shift Registers, Science Press, Beijing, 1975.   Google Scholar

show all references

References:
[1] P. B. Bhattacharya, S. K. Jain and S. R. Nagpaul, Basic Abstract Algebra, 2nd Edition, Cambridge University Press, Cambridge, 1994.  doi: 10.1017/CBO9781139174237.  Google Scholar
[2]

U. Cheng, On the cycle structure of certain classes of nonlinear shift registers, Journal of Combinatorial Theory, 37 (1984), 61-68.  doi: 10.1016/0097-3165(84)90019-0.  Google Scholar

[3]

H. Dobbertin, Kasami power functions, permutation polynomials and cyclic difference sets, Difference Sets, Sequences and Their Correlation Properties (Bad Windsheim, 1998), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 542 (1999), 133-158.   Google Scholar

[4]

S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, Calif.-Cambridge-Amsterdam, 1967.  Google Scholar

[5]

G. Gong and A. M. Youssef, Cryptographic properties of the Welch-Gong transformation sequence generators, IEEE Transactions on Information Theory, 48 (2002), 2837-2846.  doi: 10.1109/TIT.2002.804043.  Google Scholar

[6]

T. Helleseth, Nonlinear shift registers - A survey and challenges, Algebraic Curves and Finite Fields, Radon Ser. Comput. Appl. Math., De Gruyter, Berlin, 16 (2014), 121-144.   Google Scholar

[7]

K. Kjeldsen, On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions, Journal of Combinatorial Theory Ser. A, 20 (1976), 154-169.  doi: 10.1016/0097-3165(76)90013-3.  Google Scholar

[8]

K. Mandal and G. Gong, Filtering nonlinear feedback shift registers using Welch-Gong transformations for securing RFID applications, ICST Trans. Security Safety, 3 (2016), e3.   Google Scholar

[9]

J. Mykkeltveit, M. K. Siu and P. Tong, On the cycle structure of some nonlinear shift register sequences, Information and Control, 43 (1979), 202-215.  doi: 10.1016/S0019-9958(79)90708-3.  Google Scholar

[10] Z. X. Wan and Z. D. Dai, Nonlinear Feedback Shift Registers, Science Press, Beijing, 1975.   Google Scholar
Figure 1.  An Architecture of the WG-NLFSR
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347
[2]

Nataša Djurdjevac Conrad, Ralf Banisch, Christof Schütte. Modularity of directed networks: Cycle decomposition approach. Journal of Computational Dynamics, 2015, 2 (1) : 1-24. doi: 10.3934/jcd.2015.2.1
[3]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[4]

Dmitry N. Kozlov. Cobounding odd cycle colorings. Electronic Research Announcements, 2006, 12: 53-55.

[5]

Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031
[6]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
[7]

Ricardo P. Beausoleil, Rodolfo A. Montejo. A study with neighborhood searches to deal with multiobjective unconstrained permutation problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 193-216. doi: 10.3934/jimo.2009.5.193
[8]

Claudio Qureshi, Daniel Panario, Rodrigo Martins. Cycle structure of iterating Redei functions. Advances in Mathematics of Communications, 2017, 11 (2) : 397-407. doi: 10.3934/amc.2017034
[9]

Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems & Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035
[10]

Stefano Bianchini, Daniela Tonon. A decomposition theorem for $BV$ functions. Communications on Pure & Applied Analysis, 2011, 10 (6) : 1549-1566. doi: 10.3934/cpaa.2011.10.1549
[11]

Peter Müller, Gábor P. Nagy. On the non-existence of sharply transitive sets of permutations in certain finite permutation groups. Advances in Mathematics of Communications, 2011, 5 (2) : 303-308. doi: 10.3934/amc.2011.5.303
[12]

Tim Gutjahr, Karsten Keller. Equality of Kolmogorov-Sinai and permutation entropy for one-dimensional maps consisting of countably many monotone parts. Discrete & Continuous Dynamical Systems, 2019, 39 (7) : 4207-4224. doi: 10.3934/dcds.2019170
[13]

Ben Niu, Weihua Jiang. Dynamics of a limit cycle oscillator with extended delay feedback. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1439-1458. doi: 10.3934/dcdsb.2013.18.1439
[14]

Valery A. Gaiko. The geometry of limit cycle bifurcations in polynomial dynamical systems. Conference Publications, 2011, 2011 (Special) : 447-456. doi: 10.3934/proc.2011.2011.447
[15]

Zhiqin Qiao, Deming Zhu, Qiuying Lu. Bifurcation of a heterodimensional cycle with weak inclination flip. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 1009-1025. doi: 10.3934/dcdsb.2012.17.1009
[16]

Yu-Hsien Chang, Guo-Chin Jau. The behavior of the solution for a mathematical model for analysis of the cell cycle. Communications on Pure & Applied Analysis, 2006, 5 (4) : 779-792. doi: 10.3934/cpaa.2006.5.779
[17]

Domingo Gomez-Perez, Ana-Isabel Gomez, Andrew Tirkel. Arrays composed from the extended rational cycle. Advances in Mathematics of Communications, 2017, 11 (2) : 313-327. doi: 10.3934/amc.2017024
[18]

Qigang Yuan, Yutong Sun, Jingli Ren. How interest rate influences a business cycle model. Discrete & Continuous Dynamical Systems - S, 2020, 13 (11) : 3231-3251. doi: 10.3934/dcdss.2020190
[19]

Katarzyna Pichór, Ryszard Rudnicki. Applications of stochastic semigroups to cell cycle models. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2365-2381. doi: 10.3934/dcdsb.2019099
[20]

Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, J. Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 2014, 1 (2) : 391-421. doi: 10.3934/jcd.2014.1.391

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (149)
  • HTML views (503)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences