🔢 mathematics

Permutation polynomials from the trace functions

This paper establishes necessary and sufficient conditions for polynomials of the form $X+\gamma \operatorname{Tr}_{q}^{q^n}(h(X))$ to be permutation polynomials over finite fields and completely characterizes those where $h(X)$ is a specific quadratic-trace combination, including the derivation of their compositional inverses.

Original authors: Sartaj Ul Hasan, Ramandeep Kaur, Hridesh Kumar

Published 2026-08-12

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Sartaj Ul Hasan, Ramandeep Kaur, Hridesh Kumar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where numbers aren't just for counting apples or calculating scores, but are the secret ingredients in a digital lock. This is the realm of finite fields, a mathematical playground where the number of elements is fixed and finite, like a clock that only has a specific number of hours. In this world, a "permutation polynomial" is a special kind of recipe. If you feed it every single number in the set, it spits them all back out, but in a completely shuffled order, ensuring that no two inputs ever produce the same output. It's a perfect, one-to-one dance.

Why do we care about these mathematical dances? Because they are the hidden gears behind the security of your digital life. When you send a secret message or make an online purchase, your data is scrambled using these shuffling rules. To unscramble it later, you need the exact reverse dance—the "compositional inverse." If the original shuffle is a lock, the inverse is the key. Finding these perfect shuffles and their matching keys is a massive challenge for mathematicians and cryptographers, as a better shuffle means a safer digital fortress.

This paper dives deep into a specific family of these shuffling recipes. The authors, Sartaj Ul Hasan, Ramanandeep Kaur, and Hridesh Kumar, are investigating a particular structure: a simple number $X$ mixed with a "trace" function, which acts like a mathematical filter that summarizes a complex number into a simpler one. They are asking a very precise question: Under what exact conditions does this specific mixture create a perfect shuffle?

The researchers didn't just guess; they proved it. They examined several classes of these polynomials and determined the exact rules for the "mixing ingredient" (a value called $\gamma$ ) that make the shuffle work perfectly. They found that for some recipes, the ingredient must be a specific type of number, while for others, it must avoid certain values entirely. For instance, in one scenario, the mix only works if the ingredient is a "zero" or a "one," and in another, it works if the ingredient is not "one."

Perhaps most excitingly, the paper doesn't just tell us when the shuffle works; it also provides the exact recipe for the reverse dance. For the classes of polynomials they completely characterized, they wrote down the explicit formula for the compositional inverse. This means they didn't just find the lock; they forged the key. They proved that for certain conditions, the reverse formula is a specific, calculable expression involving the same trace function. Their work acts as a comprehensive guide, confirming which combinations of ingredients create a secure, reversible shuffle and which ones fail, providing a solid foundation for building more robust digital security systems.

Technical Summary: Permutation Polynomials from the Trace Functions

Problem Statement
The paper addresses the problem of determining necessary and sufficient conditions on a parameter $\gamma$ for polynomials of the form $f(X) = X + \gamma \text{Tr}_{q^n}^q(h(X))$ to be permutation polynomials (PPs) over the finite field $\mathbb{F}_{q^n}$ . Here, $q$ is a prime power, $n$ is a positive integer, and $\text{Tr}_{q^n}^q(\cdot)$ denotes the relative trace function from $\mathbb{F}_{q^n}$ to $\mathbb{F}_q$ . While numerous classes of such polynomials have been constructed in previous literature, the specific conditions on $\gamma$ for them to induce a bijection are often unknown or restricted to specific cases. Furthermore, finding explicit expressions for the compositional inverses of such PPs is generally a difficult problem with significant implications for cryptography and coding theory.

Methodology
The authors employ algebraic techniques rooted in the properties of finite fields and trace functions. The core methodology involves:

Equation Transformation: To verify if $f(X)$ is a PP, the authors analyze the equation $f(X) = a$ for an arbitrary $a \in \mathbb{F}_{q^n}$ . By substituting $X = u\gamma + a$ (where $u = \text{Tr}_{q^n}^q(h(X)) \in \mathbb{F}_q$ ), they reduce the problem to determining whether a resulting polynomial equation in $u$ has a unique solution in $\mathbb{F}_q$ for every $a$ .
Case Analysis: The proofs involve rigorous case analysis based on the value of $\gamma$ (whether $\gamma \in \mathbb{F}_q$ or $\gamma \in \mathbb{F}_{q^n} \setminus \mathbb{F}_q$ ) and the parity of the exponent $m$ (where $q=2^m$ ).
Inverse Construction: For classes identified as PPs, the authors derive explicit polynomial expressions for the compositional inverse $f^{-1}(X)$ . This is achieved by constructing auxiliary functions and utilizing lemmas that relate the trace of the function to the function itself, often leveraging the property that $f(f(X)) = X$ (involution) or by solving the system of equations derived from the trace conditions.

Key Contributions and Results

Characterization of Specific Classes over $\mathbb{F}_{q^2}$ and $\mathbb{F}_{q^3}$ :
- Theorem 3.1: For $q=2^m$ and $n=3$ , the polynomial $f(X) = X + \gamma \text{Tr}_{q^3}^q(X^2 + X^{q+1})$ is a PP over $\mathbb{F}_{q^3}$ if and only if $\gamma \in \mathbb{F}_q$ .
- Theorem 3.2 & 3.3: For $q=2^m$ $q = 2^{m}$ with $m$ $m$ odd, the authors characterize the parameter $\gamma$ $γ$ for two specific forms over $\mathbb{F}_{q^2}$ $F_{q^{2}}$ :
  - $f(X) = X + \gamma \text{Tr}_{q^2}^q(X + X^2 + X^{2q-1})$ is a PP iff $\gamma \in \{0, 1\}$ .
  - $f(X) = X + \gamma \text{Tr}_{q^2}^q(X + X^3 + X^{q+2} + X^{2q-1})$ is a PP iff $\gamma \in \{0, 1\}$ .
    These results generalize previous findings where $\gamma$ was fixed to 1.
General Characterization over $\mathbb{F}_{q^n}$ :
- Theorem 4.1: For $q=2^m$ and odd $n$ , the polynomial $f(X) = X + \gamma \text{Tr}_{q^n}^q(X^{\frac{q+q^2}{2}})$ is a PP iff $\gamma \in \mathbb{F}_q \setminus \{1\}$ . The authors provide the explicit compositional inverse: $f^{-1}(X) = X + \frac{\gamma}{\gamma+1}\text{Tr}_{q^n}^q(X^{\frac{q+q^2}{2}})$ .
- Theorem 4.2: For $q=2^m$ and any positive integer $n$ , $f(X) = X + \gamma \text{Tr}_{q^n}^q(X^3 + X^{q+2})$ is a PP iff $\gamma \in \mathbb{F}_q$ . The paper further proves that for these values, $f(X)$ is an involution (i.e., $f(f(X)) = X$ ).
Comprehensive Characterization of a General Class:
- Theorem 4.3: The paper completely characterizes the PPs of the form $f(X) = X + \gamma \text{Tr}_{q^n}^q(c_1X + c_2X^2 + X^2\text{Tr}_{q^n}^q(X))$ $f (X) = X + γ Tr_{q^{n}}^{q} (c_{1} X + c_{2} X^{2} + X^{2} Tr_{q^{n}}^{q} (X))$ where $c_1, c_2 \in \mathbb{F}_q$ $c_{1}, c_{2} \in F_{q}$ . The necessary and sufficient conditions are:
  - $\text{Tr}_{q^n}^q(\gamma) = 0$ ; OR
  - $\text{Tr}_{q^n}^q(\gamma)(c_1 + c_2^2) = 1$ and $m$ is odd.
- Proposition 4.8: The authors derive the explicit compositional inverse for the general class defined in Theorem 4.3. The inverse is given as a complex polynomial expression involving trace functions and powers of $X$ , depending on whether $\text{Tr}_{q^n}^q(\gamma) = 0$ or the second condition holds.

Significance
The paper claims significance in two primary areas:

Completing the Characterization: It provides necessary and sufficient conditions on $\gamma$ for several classes of trace-based polynomials, resolving cases where only specific instances (e.g., $\gamma=1$ ) were previously known to be PPs. This includes unifying and generalizing results from previous works by Jiang, Li, Qu, and others.
Explicit Inverses: A major contribution is the derivation of explicit polynomial expressions for the compositional inverses of these newly characterized PPs. Given that finding inverses is generally a hard problem, providing closed-form solutions for these specific classes is valuable for applications in cryptography (specifically for S-box construction in block ciphers) and coding theory.

The authors note that their results for $n=2$ encompass several lemmas from previous literature (specifically [10]), demonstrating that their general framework subsumes and extends existing knowledge.

More like this