American Institute of Mathematical Sciences

Advanced
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

* Corresponding author

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

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

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

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

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

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

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

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

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

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

Qigang Yuan, Yutong Sun, Jingli Ren. How interest rate influences a business cycle model. Discrete & Continuous Dynamical Systems - S, 2019  doi: 10.3934/dcdss.2020190
[18]

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

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 - A, 2019, 39 (7) : 4207-4224. doi: 10.3934/dcds.2019170
[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 (48)
  • HTML views (273)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences