ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Asymptotically-Tight Bounds on the Number of Cycles in Generalized de {B}ruijn-Good Graphs

Ueli Maurer

The number of cycles of length $k$ that can be generated by $q$-ary $n$-stage feedback shift-registers is studied. This problem is equivalent to finding the number of cycles of length $k$ in the natural generalization, from binary to \qa digits, of the so-called de Bruijn-Good graphs \cite{brychri,debrui}. The number of cycles of length $k$ in the \qa graph $\gqn$ of order $n$ is denoted by $\bqnk$. Known results about $\beta^{(2)}(n,k)$ are summarized and extensive new numerical data is presented. Lower and upper bounds on $\bqnk$ are derived showing that, for large $k$, virtually all \qa cycles of length $k$ are contained in $\gqn$ for $n>\tlqk$, but virtually none of these cycles is contained in $\gqn$ for $n<\tlqkm$. More precisely, if $\nyqk$ denotes the total number of \qa length $k$ cycles, then for any function $f(k)$ that grows without bounds as $k\rightarrow\infty$ (e.g. $f(k)=\log_{q}\!\log_{q}\!\log_{q}k$), the bounds obtained on $\bqnk$ are asymptotically tight in the sense that they imply \begin{eqnarray} \lki\frac{\beta^{(q)}(n(k),k)}{\nyqk}&=&0 \makebox{ for } n(k)=\lfloor\tlqkm-f(k)\rfloor, \makebox{ and} \nonumber\\ \lki\frac{\beta^{(q)}(n(k),k)}{\nyqk}&=&1 \makebox{ for } n(k)=\lfloor\tlqk+f(k)\rfloor,\nonumber \end{eqnarray} where $\lfloor.\rfloor$ denotes the integer part of the enclosed number. Finally, some approximations for $\bqnk$ are given that make the global behavior of $\bqnk$ more transparent.