Linearized polynomial Chinese remainder codes (Q7312753)

Let \(V, W\) be two finite dimensional \(\mathbb{F}_q\)-vector spaces and let \(c\in\mathrm{End}(V,W),\) the rank weight is defined as its rank considered as an endomorphism, \(w_r (c) = \mathrm{rank}(c).\) For two linear maps \(c, c^\prime\), the rank distance between them is \(d_r(c, c^\prime)= w_r (c -c^\prime).\) A rank-metric code \(\mathcal{C}\) is defined as \(\mathcal{C}\subset\operatorname{End}(V,W),\) and the code is said to be linear if it is a linear subspace of \(\textrm{End}(V,W).\)\N\NThis work presents a new code family of rank and sum-rank-metric codes called linearized Chinese Remainder Theorem (CRT) codes or \(q\)-CRT codes. In particular, let \(f_1, \ldots, f_s\in \mathbb{F}_{q^m}\langle X^q\rangle\) of \(q\)-degree respectively \(d_1, \ldots, d_s.\) Denote \(\pi_i : \mathbb{F}_{q^m}\langle X^q\rangle \rightarrow \mathbb{F}_{q^m}\langle X^q\rangle\) where \(\pi_i(g)\) is the remainder of the right division of \(g\) by \(f_i.\) Define the map \(\Pi =\pi_1 \times\cdots\times \pi_s : \mathbb{F}_{q^m}\langle X^q\rangle \rightarrow \mathbb{F}_{q^m}\langle X^q\rangle /(f_1)_l\times\cdots\times \mathbb{F}_{q^m}\langle X^q\rangle /(f_s)_l\) with \(g\mapsto (\pi_1(g), \ldots,\pi_s(g)).\) Let \(A\in \mathbb{F}_{q^m}\langle X^q\rangle\), and define the following map \(\mathcal{M}_A : \mathbb{F}_{q^m}\langle X^q\rangle\rightarrow \mathbb{F}_{q^m}\langle X^q\rangle\) where \(g\mapsto g\circ A.\) Lastly, define \(\Psi_A=\Pi\circ \mathcal{M}_A.\) For a positive integer \(k,\) denote \(\mathbb{F}_{q^m}\langle X^q\rangle_k\) the set of linearized polynomial of \(q\)-degree strictly less than \(k.\) The \(q\)CRT code associated to \(k,\) \(A\) and \(F=(f_1,\ldots, f_s)\) is \(C_{F,k,A}=\Psi_A(\mathbb{F}_{q^m}\langle X^q\rangle_k).\)\N\NAn algorithm for \(q\)-polynomial right division (RQUOREM), an extended right Euclidean algorithm for \(q\)-degree polynomials (RGCD), and an algorithm for computing left co-multipliers are presented. An algorithm to reconstruct a linearized polynomial from its remainders with respect to several moduli linearized polynomials is also established. It's shown that this algorithm runs in polynomial time in the size of the input.\N\NNext, the authors discuss linearized polynomial rings over finite fields and the effective Chinese remainder Theorem for these rings. Properties of the newly defined \(q\)CRT codes from the proposed construction are studied. It's demonstrated how others already known rank-metric codes can be obtained by this construction. The construction of parity check matrices for \(q\)CRT codes and their duals is also discussed.\N\NLastly, \(q\)CRT codes with moduli linearized polynomials with coefficients in \(\mathbb{F}_q,\) so that the map \(\Pi\) of the Chinese Remainder Theorem and its lifting do not change the support of the involved polynomials are constructed. A a probabilistic decoding algorithm is proposed, followed by an analysis of its failure rate and parameters, under the assumption that errors are uniformly distributed. It is shown that the decoding algorithm can be extended to a wider class of codes. Using parameters \(n = 200,\) \(k = 30,\) \(\alpha = 10,\) \(q = 2,\) and \(m = 100\) graphs in the paper illustrate the success probability of the decoding algorithm across three scenarios based on the rank weight of the lifted error:\N\begin{itemize}\N\item when \(l\) is small enough, the probability of recovering the full support of the lifted error remains close to 1;\N\item when \(l\) becomes larger, the probability drops before the bound given by the linear system;\N\item when \(l\) increases more, the success probability drops for smaller rank weights.\N\end{itemize}