A permutation polynomial (PP) is a polynomial over a finite field $\mathbb{F}_q$ that acts as a bijective function, shuffling the field's elements without any collisions or omissions. While monomials like $x^m$ are easy to understand—permuting the field if and only if $\gcd(m, q-1) = 1$—adding just one more term introduces complex algebraic interference. Understanding when a binomial $x^m + ax^n$ can successfully permute a field requires looking deeply at the interplay between the exponents and the field's multiplicative structure.
The Geometry of Non-Existence
Proving that a polynomial cannot be a permutation is often more challenging than constructing one that is. To rule out certain shapes of binomials, researchers rely on Hermite's Criterion. This classical result states that a polynomial $f(x)$ permutes $\mathbb{F}_q$ if and only if two conditions hold: $f(x)$ has exactly one root in $\mathbb{F}_q$, and for each power $1 \le k \le q-2$, the polynomial $f(x)^k$ reduces modulo $x^q - x$ to a degree strictly less than $q-1$.
If the reduction yields a term of degree exactly $q-1$, the polynomial fails to distribute elements evenly across the field, causing an algebraic collision.
Monomial x^m: Maps smoothly if gcd(m, q-1) = 1
Binomial x^m + ax^n: Exponents interfere -> Terms of degree q-1 emerge -> Collision!
In Nonexistence of Permutation Binomials of Certain Shapes, Michael E. Zieve leveraged this criterion to rule out simple binomial forms over prime fields $\mathbb{F}_p$. By analyzing the algebraic expansion of $(x^m + ax^n)^k$, Zieve demonstrated that when the difference between the exponents ($m-n$) shares common factors of 2 or 4 with the size of the field's multiplicative group ($p-1$), the expansion inevitably produces a forbidden $x^{p-1}$ term. This structural mismatch forces a violation of Hermite's Criterion, proving that such binomials can never be permutations.
The $\sqrt{p}-1$ Bound
When do binomials escape this trap? The answer depends on how tightly the exponent difference $m-n$ binds to the field structure. If $\gcd(m-n, p-1)$ is too small, the binomial lacks the algebraic flexibility to distribute elements uniquely.
In Permutation binomials over finite fields, Michael E. Zieve established a fundamental lower bound for binomial permutations over prime fields $\mathbb{F}_p$. The author proved that if $x^m + ax^n$ is a permutation polynomial, then:
$$\gcd(m-n, p-1) > \sqrt{p}-1$$
This inequality marks a sharp boundary for existence. If the greatest common divisor falls below this threshold, the polynomial's values collapse into a smaller subgroup of the field, making a bijection mathematically impossible. While this bound outlines where permutation binomials might exist, finding explicit constructions for large parameters remains an open challenge.
The Inversion Problem
In cryptographic applications, knowing that a polynomial permutes a field is only half the battle; one must also be able to compute its inverse. Because finite fields are discrete, the inverse of a permutation polynomial is always another polynomial, but its degree can be massive and its structure highly chaotic.
To find explicit formulas for these inverses, Fu Wang developed a framework combining piecewise decomposition and Lagrange interpolation in On inverses of some permutation polynomials over finite fields of characteristic three. By focusing on fields of characteristic three ($\mathbb{F}_{3^m}$), the author mapped out explicit inverse formulas for specialized classes of permutations, such as reversed Dickson polynomials and generalized cyclotomic mappings. This approach works by breaking the field into structural subsets where the polynomial behaves predictably, computing local inverses, and interpolating them back into a single global polynomial.
Scaling to Extension Fields
Moving from prime fields $\mathbb{F}_p$ to extension fields $\mathbb{F}_{q^n}$ introduces a vector space structure that allows for more sophisticated permutations. A particularly prized structure in cryptography is the $r$-regular complete permutation polynomial (CPP), where both $f(x)$ and $f(x)+x$ act as permutations with uniform cycle lengths.
In Regular complete permutation polynomials over quadratic extension fields, Wei Lu et al. designed a framework to construct these highly symmetric functions. However, their design is strictly bound to quadratic extension fields ($\mathbb{F}_{q^2}$).
The reason for this limitation stems from the geometric complexity of higher extensions. In a quadratic extension, the relationship between elements can be mediated by the norm and trace functions, which behave like quadratic forms. In higher-order extensions ($\mathbb{F}_{q^n}$ for $n > 2$), the algebraic varieties governing the permutation properties become multi-dimensional and lose their uniform cycle structures, presenting a steep scalability barrier for modern cryptographic protocols.
Key Foundational Work
Nonexistence of Permutation Binomials of Certain Shapes (2007) — contributed 11 concept elements to this direction.
Permutation binomials over finite fields (2009) — contributed 9 concept elements to this direction.