Nonlinear complexity from the Hermitian and the Suzuki function fields

Curves over finite and local fields (11G20) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50) Riemann surfaces; Weierstrass points; gap sequences (14H55) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Review text

Let \(s = (s_1, s_2, \ldots, s_n)\) be a sequence of length \(n \ge 1\) over the finite field \(\mathbb{F}_q\), and let \(k \in \mathbb{N}\). If \(s_i = 0\) for all \(1 \le i \le n\), the \(k\)-th order nonlinear complexity \(N^{k}(s)\) is defined to be \(0\). Otherwise, \(N^{k}(s)\) is the smallest integer \(m \in \mathbb{N}\) for which there exists a polynomial \(f \in \mathbb{F}_q[x_1, \ldots, x_m]\) of degree at most \(k\) in each variable such that\N\[\Ns_{m+I} = f(s_I, s_{I+1}, \ldots, s_{m+I-1}), \qquad I = 1, \ldots, n - m.\N\]\NSimilarly, the \(k\)-th order nonlinear complexity of \emph{total degree}, denoted by \(L^{k}(s)\), is defined as follows. If \(s_i = 0\) for all \(1 \le i \le n\), then \(L^{k}(s) = 0\). Otherwise, \(L^{k}(s)\) is the smallest \(m \in \mathbb{N}\) for which there exists a polynomial \(f \in \mathbb{F}_q[x_1, \ldots, x_m]\) of total degree at most \(k\) satisfying\N\[\Ns_{m+I} = f(s_I, s_{I+1}, \ldots, s_{m+I-1}), \qquad I = 1, \ldots, n - m.\N\]\NFor any sequence \(s\) and any \(k \in \mathbb{N}\), it is immediate that \(L^{k}(s) \geq N^{k}(s)\).\N\NThis paper investigates sequences of high nonlinear complexity arising from the Hermitian and Suzuki function fields. Relations among Hermitian triangles determined by three distinct rational points on the Hermitian function field are examined, and lower bounds for the \(k\)-th order nonlinear complexities \(N^{k}(s_n)\) and \(L^{k}(s_n)\) are established. In particular, an existing lower bound for \(L^{k}(s_n)\) is strengthened, and several possible behaviors of the \(k\)-th order nonlinear complexity associated with each type of Hermitian triangle are analyzed.\N\NMoreover, two different families of sequences are constructed using the corresponding Weierstrass semigroup, and the resulting lower bounds on \(N^{k}(s)\) and \(L^{k}(s)\) are compared. Finally, the paper studies lower bounds on \(N^{k}(s)\) and \(L^{k}(s)\) derived from the Weierstrass semigroup of two distinct rational points on a Suzuki function field over \(\mathbb{F}_q\), where \(q = 2 q_0^2\), \(q_0 = 2^t\), and \(t \geq 1\).

Cites work

This page was built for publication: Nonlinear complexity from the Hermitian and the Suzuki function fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6962824)