Eva Nuria Müller

Crosscorrelation of Non-Maximal Linear Shift Register Sequences over Fields of Odd Characteristic

German Title: Kreuzkorrelation von nicht-maximalen linearen Schieberegisterfolgen über Körpern ungerader Charakteristik

Abstract: We investigate the crosscorrelation function $C_d(t)=\sum_{i=1}^{p^n-1}\zeta^{a_{i-t}-a_{di}}$, where $\zeta$ is a complex primitive $p$-th root of unity, $(a_i)_{i \in \N}$ is a maximal linear shift register sequence of length $p^n-1$, $p$ is an odd prime. We are interested in the case where the decimation factor $d$ is {\em not} relatively prime to $p^n-1$. It will turn out that the crosscorrelation function $C_d(t)$ is not independent of the choice of $\zeta$ under these circumstances. For $p=3$, $n$ odd and $d=\frac{p^n+1}{4}+\frac{p^n-1}{2}$ we show that $2 \cdot \sqrt{p^n}$ is an upper bound for the absolute value of $1+C_d(t)$. For any odd prime $p$ and $d=p^k+1$, where $\frac{n}{\gcd{(n,k)}}$ is not divisible by 4 we determine the maximum absolute value of $C_d(t)$ and the number of values of $C_d(t)$.

German Summary: Die Kreuzkorrelation zweier $(p^n\!-\!1)$--periodischer linearer Schieberegisterfolgen $(a_i)_{i \in \N}$ und $(b_i)_{i \in \N}$ \"uber $\GF(p)$ ist durch $C_{ab}(t) = \sum_{i=0}^{p^n-1} \zeta^{a_{i-t}-b_i}$ gegeben, wobei $\zeta$ eine primitive komplexe $p$-te Einheitswurzel bezeichnet. Bei der Untersuchung der Kreuzkorrelation $C_{ab}(t)$ f\"ur $t=0, \ldots , p^n\!-\!2$ sind zwei Parameter von besonderem Interesse: die Anzahl der verschiedenen Werte von $C_{ab}(t)$ und der g\"o\"ste Absolutbetrag von $C_{ab}(t)$; es ist hierbei w\"unschenswert, da\"s beide Werte m\"oglichst klein sind. In den ersten drei Kapiteln werden die f\"ur diese Arbeit grundlegenden Begriffe definiert und erl\"autert. Im zweiten Kapitel werden ausschlie\"slich algebraische Resultate vorgestellt, die im Verlauf der Arbeit immer wieder Anwendung finden. Sie erm\"oglichen es unter anderem, im dritten Kapitel den Begriff der Dezimation einer Folge einzuf\"uhren; dies bedeutet, da\"s die Folge $(b_i)_{i \in \N}$ durch $b_i = a_{d\cdot i}$ gegeben ist. Die Kreuzkorrelation wird in diesem Fall mit $C_d(t)$ bezeichnet. Im vierten Kapitel werden die wichtigsten Korrelationseigenschaften linearer Schieberegisterfolgen sowie bereits bekannte Resultate \"uber die Verteilung von $C_d(t)$ f\"ur einige Werte von $d$ mit ggT$(d, p^n-1)=1$ vorgestellt. Ferner werden Resultate \"uber obere Schranken von $|C_{ab}(t)|$ angegeben. Neue Ergebnisse werden in Kapitel~5 pr\"asentiert. Dort werden erstmals die Korrelationseigenschaften von $C_d(t)$ f\"ur den Fall untersucht, da\"s $d$ nicht teilerfremd zu $p^n\!-\!1$, der Periodenl\"ange einer maximalen linearen Schiebergisterfolge, ist. Dies bedeutet, da\"s die Periodenl\"ange von $(b_i)_{i \in \N}$ ein echter Teiler von $p^n\!-\!1$ ist. Diese Verallgemeinerung hat zur Folge, da\"s die Verteilung von $C_{ab}(t)$ nicht mehr unabh\"angig von der Wahl der Einheitswurzel $\zeta$ ist. F\"ur den Fall $p=3$, $n$ ungerade und $d=\frac{p^n+1}{4}+\frac{p^n-1}{2}$ wird bewiesen, da"s $|C_d(t)|$ durch $1+ 2 \sqrt{p^n}$ beschr\"ankt ist. Anschlie\"send wird gezeigt, da\"s $C_d(t)$ f"ur beliebige $p \neq 2$, $n \geq 2$ und $d=p^k+1$ genau $p$ verschiedene Werte annimmt und da\"s in diesem Fall $|C_d(t)| \leq 1 + \sqrt{p^n}$ gilt. Abschlie\"send wird der Zusammenhang zwischen Folgen mit guten Korrelationseigenschaften und sogenannten $APN$-Funtionen anhand des ersten Resultates erl\"autert.

Keywords: Correlation functions, linear shift register sequences, quadratic forms

Mathematics Subject Classification (MSC91): 94A55 Shift register sequences

Language: ENG

Date of Disputation: 1998-06-11

First Referee = Advisor: Prof.Dr. Ralph-Hardo Schulz

Second Referee: Privatdozent Dr.habil. Dirk Hachenberger

Publisher: GCA Verlag der GCA mbH, Herdecke/Ruhr

ISBN: 3-928973-51-7

Related Papers: to be published in "IEEE Transactions on Information Theory"(1999)

Contact (Candidate): eva.mueller@mathematik.uni-magdeburg.de

Contact (Advisor): schulz@math.fu-berlin.de

- Created: 1999-01-08 -