Permutation polynomials from the trace functions

技术摘要：基于迹函数的置换多项式

问题陈述
本文研究了确定参数 $\gamma$ 的充分必要条件，使得形式为 $f(X) = X + \gamma \text{Tr}_{q^n}^q(h(X))$ 的多项式在有限域 $\mathbb{F}_{q^n}$ 上为置换多项式（PP）。这里，$q$ 是一个素幂，$n$ 是一个正整数，$\text{Tr}_{q^n}^q(\cdot)$ 表示从 $\mathbb{F}_{q^n}$ 到 $\mathbb{F}_q$ 的相对迹函数。虽然以往文献中已经构造了许多此类多项式的类别，但关于 $\gamma$ 使其诱导双射的具体条件往往是未知的，或者仅限于特定情形。此外，寻找此类 PP 的显式复合逆（compositional inverses）通常是一个具有重要意义但难度极大的问题，这在密码学和编码理论中具有重要影响。

研究方法
作者采用了植根于有限域和迹函数性质的代数技术。核心方法包括：

1. 方程变换：为了验证 $f(X)$ 是否为 PP，作者分析了方程 $f(X) = a$（其中 $a \in \mathbb{F}_{q^n}$ 为任意值）。通过代入 $X = u\gamma + a$（其中 $u = \text{Tr}_{q^n}^q(h(X)) \in \mathbb{F}_q$），作者将问题简化为：确定由 $u$ 构成的多项式方程在 $\mathbb{F}_q$ 中对于每个 $a$ 是否有唯一解。
2. 分类讨论：证明过程涉及基于 $\gamma$ 取值（$\gamma \in \mathbb{F}_q$ 或 $\gamma \in \mathbb{F}_{q^n} \setminus \mathbb{F}_q$）以及指数 $m$ 的奇偶性（其中 $q=2^m$）的严格分类讨论。
3. 逆构造：对于被识别为 PP 的类别，作者推导出了显式的复合逆 $f^{-1}(X)$ 的多项式表达式。这是通过构造辅助函数并利用将函数之迹与函数本身联系起来的引理来实现的，通常利用了 $f(f(X)) = X$（对合/自反性）的性质，或通过求解由迹条件导出的方程组。

主要贡献与结果

1. 针对 $\mathbb{F}_{q^2}$ 和 $\mathbb{F}_{q^3}$ 特定类别的特征化：

   • 定理 3.1：对于 $q=2^m$ 且 $n=3$，多项式 $f(X) = X + \gamma \text{Tr}_{q^3}^q(X^2 + X^{q+1})$ 是 $\mathbb{F}_{q^3}$ 上的 PP 当且仅当 $\gamma \in \mathbb{F}_q$。
   • 定理 3.2 与 3.3：对于 $m$ 为奇数的 $q=2^m$，作者刻画了 $\mathbb{F}_{q^2}$ 上两种特定形式的参数 $\gamma$：
     • $f(X) = X + \gamma \text{Tr}_{q^2}^q(X + X^2 + X^{2q-1})$ 是 PP 当且仅当 $\gamma \in \{0, 1\}$。
     • $f(X) = X + \gamma \text{Tr}_{q^2}^q(X + X^3 + X^{q+2} + X^{2q-1})$ 是 PP 当且仅当 $\gamma \in \{0, 1\}$。
       这些结果推广了以往将 $\gamma$ 固定为 1 的研究发现。

2. 针对 $\mathbb{F}_{q^n}$ 的一般特征化：

   • 定理 4.1：对于 $q=2^m$ 且 $n$ 为奇数，多项式 $f(X) = X + \gamma \text{Tr}_{q^n}^q(X^{\frac{q+q^2}{2}})$ 是 PP 当且仅当 $\gamma \in \mathbb{F}_q \setminus \{1\}$。作者提供了显式复合逆：$f^{-1}(X) = X + \frac{\gamma}{\gamma+1}\text{Tr}_{q^n}^q(X^{\frac{q+q^2}{2}})$。
   • 定理 4.2：对于 $q=2^m$ 及任何正整数 $n$，$f(X) = X + \gamma \text{Tr}_{q^n}^q(X^3 + X^{q+2})$ 是 PP 当且仅当 $\gamma \in \mathbb{F}_q$。论文进一步证明，对于这些值，$f(X)$ 是一个对合（即 $f(f(X)) = X$）。

3. 对一类通用类别的全面特征化：

   • 定理 4.3：本文完整地刻画了形式为 $f(X) = X + \gamma \text{Tr}_{q^n}^q(c_1X + c_2X^2 + X^2\text{Tr}_{q^n}^q(X))$ 的 PP（其中 $c_1, c_2 \in \mathbb{F}_q$）。其充分必要条件是：
     • $\text{Tr}_{q^n}^q(\gamma) = 0$；或者
     • $\text{Tr}_{q^n}^q(\gamma)(c_1 + c_2^2) = 1$ 且 $m$ 为奇数。
   • 命题 4.8：作者推导了定理 4.3 中定义的通用类的显式复合逆。其逆函数是一个包含迹函数和 $X$ 的幂次的复杂多项式表达式，取决于 $\text{Tr}_{q^n}^q(\gamma) = 0$ 还是满足第二个条件。

意义
该论文声称在两个主要领域具有重要意义：

1. 完成特征化：它为若干类基于迹的多项式提供了关于 $\gamma$ 的充分必要条件，解决了以往仅已知特定实例（例如 $\gamma=1$）为 PP 的情况。这包括统一并推广了 Jiang、Li、Qu 等人的先前研究结果。
2. 显式逆函数：一个主要的贡献是为这些新刻画的 PP 推导出了显式的复合逆多项式表达式。鉴于寻找逆函数通常是一个难题，为这些特定类别提供闭式解对于密码学应用（特别是分组密码中的 S-box 构建）和编码理论具有重要价值。

作者指出，他们针对 $n=2$ 的结果涵盖了以往文献（特别是 [10]）中的若干引理，表明其通用框架包含了并扩展了现有知识。