Investigating results and performance of search and
construction algorithms for word-based LFSRs, \sigma-LFSRs

J 2018

Investigating results and performance of search and construction algorithms for word-based LFSRs, \sigma-LFSRs

BISHOI, Susil Kumar a Václav MATYÁŠ

Základní údaje

Originální název

Investigating results and performance of search and construction algorithms for word-based LFSRs, \sigma-LFSRs

Autoři

BISHOI, Susil Kumar a Václav MATYÁŠ

Vydání

Discrete Applied Mathematics, Elsevier B.V. 2018, 0166-218X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.983

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/18:00100955

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Primitive polynomial; LFSR; \sigma-LFSR; Xorshift random number generator

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 2. 2. 2021 10:31, prof. RNDr. Václav Matyáš, M.Sc., Ph.D.

Anotace

V originále

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as \sigma-LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive \sigma-LFSRs. The search algorithm first constructs the \sigma-polynomial and then checks the primitiveness of the \sigma-polynomial, whereas the construction algorithm for the \sigma-LFSR, first finds a primitive polynomial f(x) and then constructs the primitive \sigma-LFSR from f(x). In this paper, we present some novel results pertaining to the search algorithm for primitive \sigma-LFSR along with the exhaustive search space complexity of the search algorithm for \sigma-LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive \sigma-LFSR. Finally, the number of \sigma-LFSRs similar to the \sigma-LFSRs generated by the construction algorithm is provided.

Návaznosti

GA16-08565S, projekt VaV

Název: Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů

Investor: Grantová agentura ČR, Advancing cryptanalytic methods through evolutionary computing

Citovat

BISHOI, Susil Kumar a Václav MATYÁŠ. Investigating results and performance of search and construction algorithms for word-based LFSRs, \sigma-LFSRs. Discrete Applied Mathematics. Elsevier B.V., 2018, roč. 243, July, s. 90-98. ISSN 0166-218X. Dostupné z: https://doi.org/10.1016/j.dam.2018.01.010.

@article{1418354,
   author = {Bishoi, Susil Kumar and Matyáš, Václav},
   article_number = {July},
   doi = {https://doi.org/10.1016/j.dam.2018.01.010},
   keywords = {Primitive polynomial; LFSR; \sigma-LFSR; Xorshift random number generator},
   language = {eng},
   issn = {0166-218X},
   journal = {Discrete Applied Mathematics},
   title = {Investigating results and performance of search and construction algorithms for word-based LFSRs, \sigma-LFSRs},
   url = {https://www.sciencedirect.com/science/article/pii/S0166218X18300660},
   volume = {243},
   year = {2018}
}

TY  - JOUR
ID  - 1418354
AU  - Bishoi, Susil Kumar - Matyáš, Václav
PY  - 2018
TI  - Investigating results and performance of search and construction algorithms for word-based LFSRs, \sigma-LFSRs
JF  - Discrete Applied Mathematics
VL  - 243
IS  - July
SP  - 90-98
EP  - 90-98
PB  - Elsevier B.V.
SN  - 0166218X
KW  - Primitive polynomial
KW  - LFSR
KW  - \sigma-LFSR
KW  - Xorshift random number generator
UR  - https://www.sciencedirect.com/science/article/pii/S0166218X18300660
L2  - https://www.sciencedirect.com/science/article/pii/S0166218X18300660
N2  - Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as \sigma-LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive \sigma-LFSRs. The search algorithm first constructs the \sigma-polynomial and then checks the primitiveness of the \sigma-polynomial, whereas the construction algorithm for the \sigma-LFSR, first finds a primitive polynomial f(x) and then constructs the primitive \sigma-LFSR from f(x). In this paper, we present some novel results pertaining to the search algorithm for primitive \sigma-LFSR along with the exhaustive search space complexity of the search algorithm for \sigma-LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive \sigma-LFSR. Finally, the number of \sigma-LFSRs similar to the \sigma-LFSRs generated by the construction algorithm is provided.
ER  -

BISHOI, Susil Kumar a Václav MATYÁŠ. Investigating results and performance of search and construction algorithms for word-based LFSRs, $\backslash$sigma-LFSRs. \textit{Discrete Applied Mathematics}. Elsevier B.V., 2018, roč.~243, July, s.~90-98. ISSN~0166-218X. Dostupné z: https://doi.org/10.1016/j.dam.2018.01.010.

Přehled o publikaci