基于全体圈个数为4的LFSR构造de Bruijn序列的研究

周琮伟; 胡斌; 关杰

doi:10.11959/j.issn.1000-436x.2022108

您当前的位置：

首页 >

文章列表页 >

基于全体圈个数为4的LFSR构造de Bruijn序列的研究

学术论文 | 更新时间：2024-06-05

- 基于全体圈个数为4的LFSR构造de Bruijn序列的研究
- Construction de Bruijn sequence based on whole LFSR with 4 cycles
- 通信学报 2022年43卷第7期页码：126-133
- 作者机构：
  
  信息工程大学密码工程学院，河南郑州 450001
- 作者简介：
  
  [ "周琮伟（1994- ），男，四川眉山人，信息工程大学博士生，主要研究方向为移位寄存器中的数学理论" ]
  [ "胡斌（1972- ），男，河南信阳人，博士，信息工程大学教授、博士生导师，主要研究方向为密码设计与分析" ]
  [ "关杰（1974- ），女，河南郑州人，博士，信息工程大学教授、博士生导师，主要研究方向为密码设计与分析" ]
- 基金信息：
  
  国家自然科学基金资助项目(61572516);国家自然科学基金资助项目(61802437)
- DOI：10.11959/j.issn.1000-436x.2022108
  中图分类号： TN918.6
- 网络首发：2022-06，
  
  纸质出版：2022-07-25
- 稿件说明：
移动端阅览
周琮伟, 胡斌, 关杰. 基于全体圈个数为4的LFSR构造de Bruijn序列的研究[J]. 通信学报, 2022,43(7):126-133.

Congwei ZHOU, Bin HU, Jie GUAN. Construction de Bruijn sequence based on whole LFSR with 4 cycles[J]. Journal on Communications, 2022, 43(7): 126-133.
周琮伟, 胡斌, 关杰. 基于全体圈个数为4的LFSR构造de Bruijn序列的研究[J]. 通信学报, 2022,43(7):126-133. DOI： 10.11959/j.issn.1000-436x.2022108.

Congwei ZHOU, Bin HU, Jie GUAN. Construction de Bruijn sequence based on whole LFSR with 4 cycles[J]. Journal on Communications, 2022, 43(7): 126-133. DOI： 10.11959/j.issn.1000-436x.2022108.

摘要

为了提高并圈法的构造效率，拓宽并圈法的应用深度，从圈结构中圈个数的角度，提出了基于全体圈个数为4的LFSR构造de Bruijn序列的方法。基于LFSR的级联特征，确定了一类级联型的反馈移位寄存器的圈结构，并据此给出了圈个数为4的n级LFSR的精确个数，以及基于全体圈个数为4的n级LFSR构造n级de Bruijn序列的全部数目。

Abstract

In order to improve the construction efficiency and widen the application depth of cycle-joining method

from the view of the number of cycles in the cycle structure

a method for constructing de Bruijn sequence based on whole LFSR with 4 cycles was proposed.Based on the characteristic of cascade connection of LFSR

the cycle structure of a class of cascaded feedback shift registers was determined.Accordingly

the exact number of whole n-order LFSR with 4 cycles was given

and the total number of n-order de Bruijn sequences constructed from whole n-order LFSR with 4 cycles as well.

关键词

Keywords

references

丁存生 , 肖国镇 . 流密码学及其应用 [M ] . 北京 : 国防工业出版社 , 1994 .

DING C S , XIAO G Z . Stream cipher and its applications [M ] . Beijing : National Defense Industry Press , 1994 .

SIEGENTHALER T . Decrypting a class of stream ciphers using ciphertext only [J ] . IEEE Transactions on Computers , 2006 , 34 ( 1 ): 81 - 85 .

RUEPPEL R A . Analysis and design of stream ciphers [M ] . Berlin : Springer , 1986 .

COURTOIS N T , MEIER W . Algebraic attacks on stream ciphers with linear feedback [C ] // 2003 International Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT) . Berlin:Springer , 2003 : 345 - 359 .

CHAN A H , GAMES R A , KEY E L . On the complexities of de Bruijn sequences [J ] . Journal of Combinatorial Theory,Series A , 1982 , 33 ( 3 ): 233 - 246 .

姜春晓 , 王佳蔚 . 高动态卫星 DSSS 信号 Turbo 迭代捕获算法 [J ] . 通信学报 , 2021 , 42 ( 8 ): 15 - 24 .

JIANG C X , WANG J W . Turbo iterative acquisition algorithm for satellite high-mobility DSSS signal [J ] . Journal on Communications , 2021 , 42 ( 8 ): 15 - 24 .

许饶琪 , 彭晓涛 , 秦世耀 , 等 . 基于M序列的双馈风机变流器参数辨识方法研究 [J ] . 电网技术 , 2022 , 46 ( 2 ): 578 - 586 .

XU R Q , PENG X T , QIN S Y , et al . Parameter identification of doubly-fed induction generator converter based on M-sequence [J ] . Power System Technology , 2022 , 46 ( 2 ): 578 - 586 .

曾理 , 成杰峰 , 孟金涛 , 等 . 使用分布式de Bruijn图遍历基因拼接并行构建和化简 [J ] . 软件学报 , 2013 , 24 ( S2 ): 140 - 149 .

CENG L , CHENG J F , MENG J T , et al . Parallelized de Bruijn graph construction and simplification for genome assembly [J ] . Journal of Software , 2013 , 24 ( S2 ): 140 - 149 .

FREDRICKSEN H . A class of nonlinear de Bruijn cycles [J ] . Journal of Combinatorial Theory,Series A , 1975 , 19 ( 2 ): 192 - 199 .

ETZION T , LEMPEL A . Algorithms for the generation of full-length shift- register sequences [J ] . IEEE Transactions on Information Theory , 1984 , 30 ( 3 ): 480 - 484 .

ANNEXSTEIN F S . Generating de Bruijn sequences:an efficient implementation [J ] . IEEE Transactions on Computers , 1997 , 46 ( 2 ): 198 - 200 .

FREDRICKSEN H . A survey of full length nonlinear shift register cycle algorithms [J ] . SIAM Review , 1982 , 24 ( 2 ): 195 - 221 .

JANSEN C J A , FRANX W G , BOEKEE D E . An efficient algorithm for the generation of de Bruijn cycles [J ] . IEEE Transactions on Information Theory , 1991 , 37 ( 5 ): 1475 - 1478 .

YANG J H , DAI Z D . Construction of m-ary de Bruijn sequences [C ] // 1992 International Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT) . Berlin:Springer , 1992 : 357 - 363 .

HAUGE E R , MYKKELTVEIT J . On the classification of de Bruijn sequences [J ] . Discrete Mathematics , 1996 , 148 ( 1/2/3 ): 65 - 83 .

MYKKELTVEIT J , SZMIDT J . On cross joining de Bruijn sequences [J ] . Contemporary Mathematics , 2015 , 632 : 333 - 344 .

GOLOMB W . Shift register sequences [M ] . Los Angeles : Aegean Park Press , 1981 .

关杰 , 周琮伟 . M序列反馈函数多项式表示的快速构造方法 [J ] . 通信学报 , 2018 , 39 ( 4 ): 84 - 90 .

GUAN J , ZHOU C W . Method of fast construction of M-sequence feedback functions with polynomial representation [J ] . Journal on Communications , 2018 , 39 ( 4 ): 84 - 90 .

高杨 , 刘松华 , 王中孝 . 一种基于“编织法”的de Bruijn序列构造算法 [J ] . 电子学报 , 2018 , 46 ( 1 ): 48 - 54 .

GAO Y , LIU S H , WANG Z X . A de Bruijn sequence construction algorithm based on ‘interleaving’ construction method [J ] . Acta Electronica Sinica , 2018 , 46 ( 1 ): 48 - 54 .

LEMPEL A . On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers [J ] . IEEE Transactions on Computers , 1970 , C-19 ( 12 ): 1204 - 1209 .

SIU M K , TONG P . Generation of some de Bruijn sequences [J ] . Discrete Mathematics , 1980 , 31 ( 1 ): 97 - 100 .

CHANG Z L , GONG G , WANG Q . Cycle structures of a class of cascaded FSRs [J ] . IEEE Transactions on Information Theory , 2020 , 66 ( 6 ): 3766 - 3774 .

LI C Y , ZENG X Y , HELLESETH T , et al . The properties of a class of linear FSRs and their applications to the construction of nonlinear FSRs [J ] . IEEE Transactions on Information Theory , 2014 , 60 ( 5 ): 3052 - 3061 .

LI C Y , ZENG X Y , LI C L , et al . A class of de Bruijn sequences [J ] . IEEE Transactions on Information Theory , 2014 , 60 ( 12 ): 7955 - 7969 .

LI C Y , ZENG X Y , LI C L , et al . Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials [J ] . IEEE Transactions on Information Theory , 2016 , 62 ( 1 ): 610 - 624 .

LI M , JIANG Y P , LIN D D . The adjacency graphs of some feedback shift registers [J ] . Designs,Codes and Cryptography , 2017 , 82 ( 3 ): 695 - 713 .

LI M , LIN D D . The adjacency graphs of LFSRs with primitive-like characteristic polynomials [J ] . IEEE Transactions on Information Theory , 2017 , 63 ( 2 ): 1325 - 1335 .

CHANG Z L , EZERMAN M F , LING S , et al . Construction of de Bruijn sequences from product of two irreducible polynomials [J ] . Cryptography and Communications , 2018 , 10 ( 2 ): 251 - 275 .

DONG Y J , TIAN T , QI W F , et al . The adjacency graphs of FSRs with a class of affine characteristic functions [J ] . Finite Fields and Their Applications , 2018 , 53 : 21 - 35 .

DONG J W , PEI D Y . Construction for de Bruijn sequences with large stage [J ] . Designs,Codes and Cryptography , 2017 , 85 ( 2 ): 343 - 358 .

董军武 , 裴定一 . 一类不可约多项式的邻接矩阵 [J ] . 数学学报(中文版) , 2018 , 61 ( 5 ): 843 - 856 .

DONG J W , PEI D Y . The adjacency matrix of some class of irreducible polynomials [J ] . Acta Mathematica Sinica (Chinese Series) , 2018 , 61 ( 5 ): 843 - 856 .

万哲先 , 代宗铎 , 刘木兰 , 等 . 非线性反馈移位寄存器 [M ] . 北京 : 科学出版社 , 1978 .

WAN Z X , DAI Z D , LIU M L , et al . Non-linear feedback shift register [M ] . Beijing : Science Press , 1978 .

ZIERLER N . Linear recurring sequences [J ] . Journal of the Society for Industrial and Applied Mathematics , 1959 , 7 ( 1 ): 31 - 48 .

MYKKELTVEIT J , SIU M K , TONG P . On the cycle structure of some nonlinear shift register sequences [J ] . Information and Control , 1979 , 43 ( 2 ): 202 - 215 .

LIDL R , NIEDERREITER H . Finite fields:encyclopedia of mathematics and its applications [J ] . Computers ＆ Mathematics with Applications , 1997 ,7:136.

浏览量

1427

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据