CS Paper Radar

New Construction of Power Functions with Low c-Differential Uniformity over Finite Fields

Zhiye Yang, Yan Wang, Keqin Feng

cs.IT ·submitted 2026-09-19 04:43 UTC · v1
theory

Abstract

This paper investigates the $c$-differential uniformity of power functions over finite fields, an important class of cryptographic functions with favorable differential properties. Specifically, for finite fields $\mathbb{F}_q$ satisfying $q-1=en$ with $e\ge 3$ and $e\mid n$, we prove that there exists $c\in\mathbb{F}_q\setminus\{0,1,ε,\dots,ε^{e-1}\}$, where $ε$ is an $e$-th primitive root of unity in $\mathbb{F}_q^*$, the constructed power functions $f(x)=x^{ln+1}$ with $1\le l\le e-1$ and $\gcd(l,e)=1$ satisfy the upper bound $Δ(f,c)\le e$, provided that certain cyclotomic conditions hold. We show that our conditions are mild; namely, such power functions can be constructed over infinitely many extension fields $\mathbb{F}_q$ of $\mathbb{F}_p$ for any given $e\ge 3$ and prime $p$ with $p\nmid e$. Furthermore, based on the Weil bound for multiplicative character sums, we prove that the obtained upper bound is tight for sufficiently large $q$, demonstrating the optimality of our results. We also analyze the special case $c=-1$ and derive simplified explicit conditions. In particular, we explicitly characterize the admissible parameters for the case $e=3$ and present concrete function examples for practical validation.

Closest papers

Nearest neighbours by meaning across the whole index.

On the maximum length of cyclic MDS codes

cs.IT ·2026-10-21 ·Gaojun Luo, Xiwang Cao, Shitao Li, Yang Li
theoryhot direction similarity 0.64
Abstract

We study the maximum length of nontrivial simple-root cyclic maximum distance separable (MDS) codes over ${\mathbb F}_q$. We prove $n\le q+1$ if $\gcd(n,q^2-1)>2$, or if the dimension is even and $\gcd(n,q^2-1)>1$. The bound also holds for all lengths whose prime factors lie in $\{2,3,5,7\}$. We obtain further cases involving primes $\ell\ge11$ with $(\ell-1)/2$ prime, under conditions on the exponents and the characteristic. The proofs combine Fourier supports, locality bounds and field descent with arithmetic restrictions on multiplicative orders and prime-adic valuations.

0.22

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.63
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

Minimum distances of primitive narrow-sense BCH codes via good zero-sets

cs.IT ·2026-09-18 ·Run Zheng
similarity 0.61
Abstract

Determining the exact minimum distances of BCH codes remains a open problem. We establish the minimum distances of several families of primitive narrow-sense BCH codes, showing that they attain their designed distances. Our approach centers on $\mathbb{F}_q$-good zero-sets, which we introduce through a derivative condition on their vanishing polynomials. We show that a $q$-ary primitive narrow-sense BCH code of length $q^m-1$ and designed distance $2\leqδ\leq q^m-1$ has minimum distance $δ$ if and only if there exists an $\mathbb{F}_q$-good zero-set of cardinality $δ+1$ in the finite field $\mathbb{F}_{q^m}$ with $q^m$ elements. To construct $\mathbb{F}_q$-good zero-sets, we develop several methods based on polynomial substitutions, power maps, and shifted inverses, as well as direct constructions using polynomials of special forms. Together with suitable initial $\mathbb{F}_q$-good zero-sets, including those arising from known minimum-distance results, these methods yield new good zero-sets of various cardinalities and hence families of primitive narrow-sense BCH codes whose minimum distances equal their designed distances. These families cover a broad range of designed distances, with several known minimum-distance results recovered as special cases.

0.38

Cyclotomic polynomials with trinomial irreducible factors over finite fields

cs.IT math.NT ·2026-10-31 ·Li Zhu, Hongfeng Wu
similarity 0.60
Abstract

We classify the pairs $(q,n)$, where $q$ is a prime power, $n>1$, and $\gcd(n,q)=1$, for which every irreducible factor of $Φ_n(x)$ over $\F_q$ has exactly three nonzero terms. The positive support exponents of these factors have a common greatest common divisor, which gives a unique reduction by a power substitution. The reduced degree is two in odd characteristic and belongs to $\{2,3,4\}$ in characteristic two; the cubic and quartic cases arise by scalar substitution from the layers of orders $7$ and $15$. This yields necessary and sufficient arithmetic conditions on $(q,n)$ and explicit factorizations. Among the classified families, precisely those arising from quartic bases have a divisor layer containing an irreducible factor with more than three terms.

0.33

Support periods of polynomials and support-primitive decomposition of constacyclic codes over Galois rings

cs.IT math.NT ·2026-10-21 ·Li Zhu, Hongfeng Wu
similarity 0.59
Abstract

Let \(A=\GR(p^e,r)\) have residue field \(\F_q\), and let \(λ\in A^\times\). We relate coefficient compression of monic divisors of \(X^N-λ\) to support-primitive decomposition of constacyclic codes. At a simple-root length, the support period of every nonconstant monic divisor is preserved at each coefficient precision and equals the order of the multiplicative stabilizer of its root set. For a cyclic Frobenius-orbit polynomial, the multiple equal-difference structure determines its support period, core degree, and least relative degree of an unramified extension over which all its basic-irreducible factors are binomials. Coordinate projections give every constacyclic code over a finite commutative ring a unique maximal interleaving into copies of one support-primitive code. At simple-root lengths over \(A\), the intrinsic period of a code is the greatest common divisor of the periods of its torsion codes. The decomposition yields distance and duality formulas and the arithmetic Singleton bound for free codes. At every length, a nonzero code over \(A\) has the same minimum Hamming distance as its highest torsion code, which gives a refined bound. At repeated-root lengths, identical torsion filtrations can occur with different intrinsic periods, while a class of nonzero codes obtained by substitution from simple-root generators retains the same core and minimum distance. Trace matrices recover the coefficients of basic-irreducible cores using unit pivots, and local Hensel corrections lift compressed factors directly. For \(X^n-1\) with \(p\nmid n\), lifting and output have quasi-linear bit cost in the compressed representation when the arithmetic data and residue factorizations are given.

0.25

Complete characterization of the differential spectrum of a Niho type power function

cs.IT ·2026-08-12 ·Nian Li, Xi Xie, Rui Xu, Yi Yu, Xiangyong Zeng
similarity 0.59
Abstract

Power functions with Niho exponents have attracted considerable attention due to their important applications in sequence design, coding theory, and cryptography. This paper investigates the differential properties of Niho type power functions of the form $F(x)=x^{s(2^m-1)+1}$ over $\mathbb{F}_{2^{2m}}$ with $2\leq s\leq 2^m$. We first establish a general characterization of the differential spectrum of $F(x)$ having at most three nonzero values via its Walsh spectrum. Focusing subsequently on the case $s=(2^k+1)^{-1} \pmod{2^m+1}$ where $\gcd(k,m)=e$, we employ a refined analysis of the number of solutions to certain equations over finite fields. Specifically, it is proved that $F(x)$ is locally differentially $2^e$-uniform when $\gcd(2^k-1,2^m+1)=2^e+1$ and locally differentially $(2^{2e}-2^e)$-uniform when $\gcd(2^k-1,2^m+1)=1$, and their differential spectra are completely determined. These results completely characterize the differential properties of this family and yield new infinite families of locally differentially $4$-uniform power functions.

0.04

Good rational functions up to degree six

cs.IT math.NT ·2026-11-02 ·Anuvrat Jaindungarwal, Divyesh Vaghasiya
similarity 0.58
Abstract · 14 pages, 1 table

Locally recoverable codes (LRCs) are fundamental to the architecture of modern distributed storage systems. The Tamo-Barg construction of optimal LRCs was revolutionized by the introduction of good polynomials, which group evaluation points into local recovery sets. However, polynomial constructions are constrained by their inherently large Galois groups, which limit the number of totally split rational places. Recent advances have generalized this paradigm to good rational functions, which leverage the geometry of the projective line to achieve minimal Galois groups and subsequently codes with greater length. In this paper, we complete the classification of good rational functions of degree up to $6$ in characteristic $2$. By embedding the problem into algebraic function field theory, we explicitly determine the minimal arithmetic and geometric Galois groups for these low degrees. Furthermore, we move beyond asymptotic Hasse-Weil estimates by proving that the exact number of totally split places over extension fields obeys a linear recurring sequence (LRS). This gives an efficient method for computing the exact lengths and dimensions of the corresponding optimal LRCs and, in many cases, yields parameters beyond those obtainable from good polynomials.

0.24

On cyclic codes generated by cyclotomic polynomials

cs.IT ·2026-11-18 ·Alonso S. Castellanos, Gyan Morales Solis, Guilherme Tizziotti
similarity 0.58
Abstract

Let $n$ be a composite positive integer coprime to $\operatorname{char}(\mathbb{F}_q)$ and let $t = \operatorname{lpf}(n)$ be the least prime factor of $n$. In this paper we study the cyclic codes $\mathcal{C}_{n,t} = \langle Q_n(X)Q_t(X)\rangle$ and $\mathcal{C}_{n,t,1} = \langle Q_n(X)Q_t(X)Q_1(X)\rangle$ over $\mathbb{F}_q$, where $Q_d(X)$ denotes the $d$-th cyclotomic polynomial. These codes extend the families $\mathcal{C}_n = \langle Q_n(X)\rangle$ and $\mathcal{C}_{n,1} = \langle Q_n(X)Q_1(X)\rangle$ recently studied by Bhagat and Sarma. We determine the exact minimum distances of $\mathcal{C}_{n,t}$ and $\mathcal{C}_{n,t,1}$, showing that $d(\mathcal{C}_{n,t,1}) = 2t$ and that $d(\mathcal{C}_{n,t})$ equals $t$ if $t^2 \nmid n$, and $2t$ if $t^2 \mid n$. For the dual codes, we establish $d(\mathcal{C}_{n,t}^\perp) = 2^{ω(n)}$, handling the case $ω(n) \le 2$ via the Hartmann--Tzeng bound, and the case $ω(n) \ge 3$ via a direct-sum decomposition $\mathcal{C}_{n,t}^\perp = \mathcal{C}_n^\perp \oplus \mathcal{V}_t$ and the tensor-product structure of $\mathcal{C}_n^\perp$ over its prime-power components. As applications, we show that all four code families are linear complementary dual (LCD) and locally recoverable (LRC), and we determine their locality parameters, identifying several infinite families that are $r$-optimal or $d$-optimal with respect to the Singleton-type bound for LRC codes.

0.25