Quadratic functions with prescribed spectra
type: Item
instance of: scholarly article
title: Quadratic functions with prescribed spectra
zbMATH Open document ID: 1284.11156
author: Wilfried Meidl
author: Alev Topuzoğlu
published in: Designs, Codes and Cryptography
publication date: 2013-01-28T00:00:00Z
full work available at URL: 92.pdf
review text: 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)].
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6131781
zbMATH Keywords: quadratic functions
zbMATH Keywords: trace forms
zbMATH Keywords: plateaued functions
zbMATH Keywords: semi-bent functions
zbMATH Keywords: self-reciprocal polynomials
zbMATH Keywords: linear complexity
MaRDI profile type: Publication
OpenAlex ID: W1975768884
cites work: Q3062258
cites work: On the construction of bent vectorial functions
cites work: A construction of weakly and non-weakly regular bent functions
cites work: Bent Functions of Maximal Degree
cites work: On Bent and Semi-Bent Quadratic Boolean Functions
cites work: Fast Algorithms for Determining the Linear Complexity of Sequences Over&lt;tex&gt;$hboxGF,(p^m)$&lt;/tex&gt;With Period&lt;tex&gt;$2^tn$&lt;/tex&gt;
cites work: Q4823178
cites work: Highly degenerate quadratic forms over finite fields of characteristic 2
cites work: Trace forms over finite fields of characteristic 2 with prescribed invariants
cites work: A fast algorithm for determining the complexity of a binary sequence with period&lt;tex&gt;2^n&lt;/tex&gt;(Corresp.)
cites work: Q4695307
cites work: A new characterization of semi-bent and bent functions on finite fields
cites work: Construction of bent functions from near-bent functions
cites work: Q3509721
cites work: Shift-register synthesis and BCH decoding
cites work: On the expected value of the linear complexity and the k-error linear complexity of periodic sequences
cites work: Reducing the calculation of the linear complexity of \(u_2^v\)-periodic binary sequences to Games-Chan algorithm
cites work: On the construction of irreducible self-reciprocal polynomials over finite fields
cites work: Factorization of a class of polynomials over finite fields
cites work: A fast algorithm for determining the linear complexity of a sequence with period \(p^n\) over GF\((q)\)
cites work: Q4417388
DOI: 10.1007/S10623-012-9690-6
description: scientific article; zbMATH DE number 6131781