Algorithms for the generation of full-length shift- register sequences

Author

Etzion, Tuvi ; Lempel, Abraham

Volume

Issue

fYear

1984

fDate

5/1/1984 12:00:00 AM

Firstpage

480

Lastpage

484

Abstract

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates $2^{k \\cdot g(n,k)}$ full cycles of length $2^{n}$ , using $3n + k \\cdot g(n, k)$ bits of storage, where $k$ is a free parameter in the range $1 \\leq k \\leq 2^{((n-4)/2)}$ , and $g(n, k)$ is of the order of $n - 2 \\log k$ . The second algorithm generates about $2^{n^{2}/4}$ full cycles of length $2^{n}$ , using about $n^{2}/2$ bits of storage. In both algorithms, the time required to produce the next bit from the last $n$ bits is close to $n$ . A possible application to the construction of stream ciphers is indicated.

Keywords

Shift-register sequences; Computer science; Cryptography; Registers; State feedback;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1984.1056919

Filename

1056919

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=938958