Enumeration of linear transformation shift registers

详细信息    查看全文

• 作者：Samrith Ram (1)
  
  1. Institut de Math茅matiques de Luminy ; Luminy Case 907 ; 13288 ; Marseille Cedex 9 ; France
  
• 关键词：Block companion matrix ; Linear feedback shift register (LFSR) ; Self ; reciprocal polynomial ; Splitting subspace ; Transformation shift register (TSR) ; 12E05 ; 15A33 ; 11T71
• 刊名：Designs, Codes and Cryptography
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：75
• 期：2
• 页码：301-314
• 全文大小：187 KB
• 参考文献：1. Ahmadi O.: Generalization of a theorem of Carlitz. Finite Fields Appl. 17(5), 473鈥?80 (2011).
  2. Carlitz L.: Some theorems on irreducible reciprocal polynomials over a finite field. J. Reine Angew. Math. 227, 212鈥?20 (1967).
  3. Chen E., Tseng D.: The splitting subspace conjecture. Finite Fields Appl. 24, 15鈥?8 (2013).
  4. Cohen S.D.: On irreducible polynomials of certain types in finite fields. Proc. Camb. Philos. Soc. 66, 335鈥?44 (1969).
  5. Dewar M., Panario D.: Linear transformation shift registers. IEEE Trans. Inf. Theory 49(8), 2047鈥?052 (2003).
  6. Dewar M., Panario D.: Mutual irreducibility of certain polynomials. In: Mullen, G.L., Poli, A., Stichtenoth, H. (eds.) Finite Fields and Applications, Volume 2948 of Lecture Notes in Computer Science, pp. 59鈥?8. Springer, Berlin (2004).
  7. Gerstenhaber M.: On the number of nilpotent matrices with coefficients in a finite field. Ill. J. Math. 5, 330鈥?33 (1961).
  8. Ghorpade S.R., Hasan S.U., Kumari M.: Primitive polynomials, singer cycles and word-oriented linear feedback shift registers. Des. Codes Cryptogr. 58(2), 123鈥?34 (2011).
  9. Ghorpade S.R., Ram S.: Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields. Finite Fields Appl. 17(5), 461鈥?72 (2011).
  10. Ghorpade S.R., Ram S.: Enumeration of splitting subspaces over finite fields. In: Aubry, Y., Ritzenthaler, C., Zykin, A. (eds.) Arithmetic, Geometry, Cryptography and Coding Theory, Volume 574 of Contemporary Mathematics, pp. 49鈥?8. American Mathematical Society, Providence (2012).
  11. Hasan S.U., Panario D., Wang Q.: Word-Oriented Transformation Shift Registers and Their Linear Complexity. SETA, Volume 7280 of Lecture Notes in Computer Science, pp. 190鈥?01. Springer, Berlin (2012).
  12. Lidl R. Niederreiter H.: Finite Fields, Volume 20 of Encyclopedia of Mathematics and its Applications, 2nd edn. Cambridge University Press, Cambridge (1997).
  13. Meyn H.: On the construction of irreducible self-reciprocal polynomials over finite fields. Appl. Algebra Eng. Commun. Comput. 1(1), 43鈥?3 (1990).
  14. Meyn H., G枚tz W.: Self-reciprocal polynomials over finite fields. Publ. I.R.M.A. Strasbourg 413(S-21), 82鈥?0 (1990).
  15. Miller R.L.: Necklaces, symmetries and self-reciprocal polynomials. Discret. Math. 22(1), 25鈥?3 (1978).
  16. Niederreiter H.: The multiple-recursive matrix method for pseudorandom number generation. Finite Fields Appl. 1(1), 3鈥?0 (1995).
  17. Preneel B. (ed.): Introduction to the Proceedings of the Second Workshop on Fast Software Encryption (Leuven, Belgium, Dec 1994), Volume 1008 of Lecture Notes in Computer Science. Springer, Heidelberg (1995).
  18. Reiner I.: On the number of matrices with given characteristic polynomial. Ill. J. Math. 5, 324鈥?29 (1961).
  19. Tsaban B., Vishne U.: Efficient linear feedback shift registers with maximal period. Finite Fields Appl. 8(2), 256鈥?67 (2002).
  20. Zeng G., Han W., He K.: High efficiency feedback shift register: \(\sigma \) -lfsr. Cryptology ePrint Archive, Report 2007/114. http://eprint.iacr.org/2007/114 (2007). Accessed 2 Dec 2013
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586

文摘

We consider the problem of counting the number of linear transformation shift registers (TSRs) of a given order over a finite field. We derive explicit formulae for the number of irreducible TSRs of order two. An interesting connection between TSRs and self-reciprocal polynomials is outlined. We use this connection and our results on TSRs to deduce a theorem of Carlitz on the number of self-reciprocal irreducible monic polynomials of a given degree over a finite field.