Technical Report CS0245

Title: Algorithms for the Generation of Full-length Shift-register Sequences
Authors: Tuvi Etzion and Abraham Lempel
Abstract: This paper presents two aigoritnms for the generation of full-length, shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates 2^(k*g(n,k)) full cycles of length 2^n, using 3n+k*g(p,k) bits of storage, where k is a free parameter in the range 1<=k<=2^((n-4)/2), and g(n,k) is of the order of n-2*logk. The second algorithm generates about 2^((n^2)/4) full cycles of length 2^n, using about (n^2)/2 bits of strorage. 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 construcion of stream ciphers is indicated.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1982
To the main CS technical reports page

Computer science department, Technion