Characterizations and constructions of n-to-1 mappings over finite fields

Abstract

$n$-to-$1$ mappings have wide applications in many areas, especially in cryptography, finite geometry, coding theory and combinatorial design. In this paper, many classes of $n$-to-$1$ mappings over finite fields are studied. First, we provide a characterization of general $n$-to-$1$ mappings over ${\mathbb{F}}_{p^m}$ by means of the Walsh transform. Then, we completely determine $3$-to-$1$ polynomials with degree no more than $4$ over ${\mathbb{F}}_{p^m}$. Furthermore, we obtain an AGW-like criterion for characterizing an equivalent relationship between the $n$-to-$1$ property of a mapping over finite set $A$ and that of another mapping over a subset of $A$. Finally, we apply the AGW-like criterion into several forms of polynomials and obtain some explicit $n$-to-$1$ mappings. Especially, three explicit constructions of the form $x^{r}h\left(x^s\right)$ from the cyclotomic perspective, and several classes of $n$-to-$1$ mappings of the form $g\left(x^{q^k}-x+\delta \right)+cx$ are provided.

23 pages, submitted to a journel

Cited by in corpus (1)

• On many-to-one mappings over finite fields