Quadratic functions with prescribed spectra (Q1934217): Difference between revisions
From MaRDI portal
Latest revision as of 04:02, 6 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Quadratic functions with prescribed spectra |
scientific article |
Statements
Quadratic functions with prescribed spectra (English)
0 references
28 January 2013
0 references
Let \(p\) be a prime and let \(f: \mathbb F_{p^n}\to \mathbb F_p\) be a quadratic function. The Walsh transform at \(b\in\mathbb F_{p^n}\) is: \[ \hat f(b)=\sum_{x\in\mathbb F_{p^n}} \varepsilon_p^{f(x)-\text{Tr}(bx)}, \] where \(\varepsilon_p=e^{2\pi i/p}\). It is well-known that \(f\) is \(s\)-plateaued, for some \(0\leq s\leq n-1\), meaning that all \(|\hat f(b)|^2\) lie in \(\{ 0, p^{n+s}\}\). Every quadratic function can be written as a trace form. The authors consider the special class of trace forms where the coefficients are in the base field: \[ \mathcal F_{p,n}(x)=\text{Tr}\left(\sum_{i=0}^k a_ix^{p^i+1}\right), \quad a_i\in\mathbb F_p. \] They consider four problems: -- Given \(s\), determine \(n\) such that all \(\mathcal F_{p,n}\) are \(s\)-plateaued. -- Given \(n\), find possible \(s\) with some \(\mathcal F_{p,n}\) \(s\)-plateaued. -- Given \(n\) and an \(s\) known to give rise to an \(s\)-plateaued \(\mathcal F_{p,n}\), construct an \(s\)-plateaued \(\mathcal F_{p,n}\). -- Given \(n\), for any \(s\), enumerate all \(s\)-plateaued \(\mathcal F_{p,n}\). Numerous partial results are known for all four problems. The authors unify these and extend them to arbitrary characteristic. To be specific, they completely answer (1) and (2). Problem (3) is solved for all \(s\) and all odd \(n\) prime to \(p\). They solve (4) for \(p=2\) and \(n=2^m\), \(m\geq 2\) as well as for odd \(p\) and \(n=q^m\), where \(q\) is an odd prime for which \(p\) is a primitive root modulo \(q^2\). The major tools used are: self-reciprocal factors of cyclotomic polynomials and two algorithms for computing linear complexity, one due to \textit{R. A. Games} and \textit{A. H. Chan} [IEEE Trans. Inf. Theory 29, 144--146 (1983; Zbl 0498.68034)] and the other due to \textit{G. Xiao, S. Wei, K.Y. Lam} and \textit{K. Imamura} [IEEE Trans. Inf. Theory 46, 2203--2206 (2000; Zbl 0997.94013)].
0 references
quadratic functions
0 references
trace forms
0 references
plateaued functions
0 references
semi-bent functions
0 references
self-reciprocal polynomials
0 references
linear complexity
0 references
0 references
0 references
0 references