Construction of de Bruijn sequences from product of two irreducible polynomials
We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a s...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/83380 http://hdl.handle.net/10220/43538 |
| _version_ | 1826111976851374080 |
|---|---|
| author | Chang, Zuling Ezerman, Martianus Frederic Ling, San Wang, Huaxiong |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chang, Zuling Ezerman, Martianus Frederic Ling, San Wang, Huaxiong |
| author_sort | Chang, Zuling |
| collection | NTU |
| description | We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly. |
| first_indexed | 2024-10-01T02:59:36Z |
| format | Journal Article |
| id | ntu-10356/83380 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:59:36Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | ntu-10356/833802023-02-28T19:32:49Z Construction of de Bruijn sequences from product of two irreducible polynomials Chang, Zuling Ezerman, Martianus Frederic Ling, San Wang, Huaxiong School of Physical and Mathematical Sciences Binary periodic sequence De Bruijn sequence We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial f(x) = p(x)q(x) where p(x) and q(x) are distinct irreducible polynomials in F2[x]. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly. MOE (Min. of Education, S’pore) Accepted version 2017-08-03T07:35:37Z 2019-12-06T15:21:12Z 2017-08-03T07:35:37Z 2019-12-06T15:21:12Z 2017 Journal Article Chang, Z., Ezerman, M. F., Ling, S., & Wang, H. (2017). Construction of de Bruijn sequences from product of two irreducible polynomials. Cryptography and Communications, 10(2), 251-275. 1936-2447 https://hdl.handle.net/10356/83380 http://hdl.handle.net/10220/43538 10.1007/s12095-017-0219-8 197355 en Cryptography and Communications © 2017 Springer Science+Business Media New York. This is the author created version of a work that has been peer reviewed and accepted for publication by Cryptography and Communications, Springer Science+Business Media New York. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1007/s12095-017-0219-8]. 26 p. application/pdf |
| spellingShingle | Binary periodic sequence De Bruijn sequence Chang, Zuling Ezerman, Martianus Frederic Ling, San Wang, Huaxiong Construction of de Bruijn sequences from product of two irreducible polynomials |
| title | Construction of de Bruijn sequences from product of two irreducible polynomials |
| title_full | Construction of de Bruijn sequences from product of two irreducible polynomials |
| title_fullStr | Construction of de Bruijn sequences from product of two irreducible polynomials |
| title_full_unstemmed | Construction of de Bruijn sequences from product of two irreducible polynomials |
| title_short | Construction of de Bruijn sequences from product of two irreducible polynomials |
| title_sort | construction of de bruijn sequences from product of two irreducible polynomials |
| topic | Binary periodic sequence De Bruijn sequence |
| url | https://hdl.handle.net/10356/83380 http://hdl.handle.net/10220/43538 |
| work_keys_str_mv | AT changzuling constructionofdebruijnsequencesfromproductoftwoirreduciblepolynomials AT ezermanmartianusfrederic constructionofdebruijnsequencesfromproductoftwoirreduciblepolynomials AT lingsan constructionofdebruijnsequencesfromproductoftwoirreduciblepolynomials AT wanghuaxiong constructionofdebruijnsequencesfromproductoftwoirreduciblepolynomials |