TR#: | CS0245 |

Class: | CS |

Title: | Algorithms for the Generation of Full-length Shift-register Sequences |

Authors: | Tuvi Etzion and Abraham Lempel |

CS0245.pdf | |

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. |

Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1982/CS/CS0245), 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