Generalization of \(m\)-sequences and fast generation of a class of \(M\)- sequences (Q1179327)

A fast generating algorithm of a class of \(M\)-sequences over the finite field \(GF(q^ m)\) is proposed. Let \(\{a_ i\}=\{Tr^{mn}_ m(\Theta\gamma^ i), i=0,1,2,\ldots\}\) be an \(m\)-sequence over \(GF(q^ m)\) where \(\gamma\) is a primitive element of \(GF(q^{mn})^*\) and \(\Theta\in GF(q^{mn})^*\), \(Tr^{mn}_ m\) is a trace function from \(GF(q^{mn})\) to \(GF(q^ m)\). Let \(T=(q^{mn}-1)/q^ m-1\), \(\eta=\gamma^ T\) and \(a^ T=a_ 0,a_ 1,\dots,a_{T-1}\), then it is easy to see that \(\{a_ i\}=\eta^ 0a^ T,\eta^ 1a^ T,\ldots,\eta^{q^ m-2}a^ T,\ldots\). Choose \(\Theta\) such that \(a_ 0=a_ 1=\ldots=a_{n-2}=0\). Let \(e_ 0,e_ 1,\ldots,e_{m-1}\) be a fixed basis of \(GF(q^ m)\) over \(GF(q)\) and \(a_ i=\sum^{m- 1}_{j=0}b_{ij}e_ j\), \(b_{ij}\in GF(q)\). For any basis \(e_ 0',e_ 1',\ldots,e_{m-1}'\) of \(GF(q^ m)\) over \(GF(q)\), define the sequence \(a_ i'=\sum^{m-1}_{j=0}b_{ij}e_ j'\), \(i=0,1,2,\ldots\). It is proved that the sequence \(\{e_ i\}=a'(p(0)),a'(p(1)),\ldots,a'(p(q^ m-2))\), inserted a zero between \(a'(p(i))\) and \(a'(p(i+1))\) for some \(i\), is an \(M\)-sequence over \(GF(q^ m)\) where \(a'(k)=a_{kT}',a_{kT+1}',\ldots,a_{kT+T-1}'\) and \(p\) is a permutation on \(\mathbb{Z}_{q^ m-1}\).