🔢 mathematics

Inverses of six classes of permutation polynomials of the form $x+\gamma\operatorname{Tr}_q^{q^2}(h(x))$ over finite fields of even characteristic

本文针对有限域 $\mathbb{F}_{q^2}$ （其中 $q=2^n$ ）上形如 $x+\gamma\operatorname{Tr}_q^{q^2}(h(x))$ 的置换多项式，求出了六类此类多项式的复合逆。

原作者： Rajesh P. Singh, Dinesh Kumar, Jitendra Prakash

发布于 2026-04-22

📖 1 分钟阅读🧠 深度阅读

原作者： Rajesh P. Singh, Dinesh Kumar, Jitendra Prakash

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文听起来充满了高深的数学符号，但如果我们把它想象成一个**“数字世界的锁与钥匙”**的故事，就会变得非常有趣。

想象一下，你有一个巨大的、由 0 和 1 组成的数字迷宫（数学家称之为“有限域”）。在这个迷宫里，有一群特殊的**“捣蛋鬼”**（数学家称之为“置换多项式”）。

1. 什么是“捣蛋鬼”？（置换多项式）

在这个迷宫里，普通的规则是：你输入一个数字，机器输出另一个数字。
但“捣蛋鬼”很特别，它们有一种**“打乱顺序”的超能力。如果你把迷宫里所有的数字（从 1 到 N）都扔进去，它们会出来，但顺序完全变了，而且每个数字都只出现一次，绝不重复，也绝不遗漏**。

在密码学（比如保护你的银行卡密码）中，这种“打乱顺序”的能力非常有用，因为它能让信息变得难以被破解。

2. 问题的核心：如何找回钥匙？（求逆）

现在，假设你有一个“捣蛋鬼”把数据打乱了。如果你想要恢复原始数据，你就需要一把**“反向钥匙”**（数学家称之为“复合逆”）。

正向过程：输入 A $\rightarrow$ 捣蛋鬼 $\rightarrow$ 输出乱序的 B。
逆向过程：输入乱序的 B $\rightarrow$ 钥匙 $\rightarrow$ 还原回 A。

难点在于：虽然我们知道这把“钥匙”肯定存在（因为捣蛋鬼没有把任何数字弄丢），但找到这把钥匙的具体形状（数学公式）非常困难。就像你知道有人把一副扑克牌洗乱了，但你要写出一个公式，能瞬间把牌洗回原样，这太难了！

3. 这篇论文做了什么？

作者 Rajesh P. Singh 和他的团队，就像一群**“顶级锁匠”**。他们发现了一类特定的“捣蛋鬼”（论文标题里提到的 $x + \gamma \text{Tr}(h(x))$ 这种形式的多项式）。

之前，其他学者（Jiang 等人）已经发现了这六类捣蛋鬼，并确认它们确实能把数字打乱。但这篇论文要做的是：为这六类捣蛋鬼，分别打造出了六把精确的“钥匙”（逆多项式公式）。

4. 他们是怎么做到的？（简单的比喻）

为了找到钥匙，作者没有盲目地乱试，而是使用了一些聪明的**“魔法工具”**（辅助引理）：

工具一：特殊的镜子（迹函数 Tr）
想象有一个特殊的镜子，能把迷宫里的复杂数字“投影”到一个更简单的平面上。作者利用这个镜子的特性，把复杂的打乱过程拆解成了简单的步骤。
工具二：解方程的拼图
他们把“如何还原”这个问题，变成了解一个复杂的拼图游戏。通过巧妙的代数运算（就像在解一个超级复杂的方程组），他们把“钥匙”的每一个零件都拼了出来。

5. 为什么这很重要？

你可能会问：“这跟我有什么关系？”

保护隐私：在像 AES（高级加密标准）这样的现代加密系统中，这种“打乱”和“还原”的过程是核心。如果我们有更简单、更清晰的公式来生成这些“钥匙”，计算机处理加密和解密的速度就会更快，安全性也可能更高。
纠错：在数据传输中（比如你发微信、看视频），如果数据在传输中出错了，这些数学工具能帮助系统自动发现并修复错误，就像把被弄乱的文件瞬间复原一样。

总结

简单来说，这篇论文就是为六种特定的“数字打乱机器”找到了对应的“一键还原”说明书。

以前，我们只知道这些机器能工作，但不知道如何高效地让它们“倒带”。现在，作者给出了明确的数学公式，让计算机工程师可以更方便地利用这些工具来保护我们的数字世界。这就好比他们不仅发现了新的锁，还顺手把开锁的万能钥匙也造出来了！

这是一份关于论文《Inverses of six classes of permutation polynomials of the form $x+\gamma \text{Tr}_{q^2}^q (h(x))$ over finite fields of even characteristic》（偶特征有限域上形式为 $x+\gamma \text{Tr}_{q^2}^q (h(x))$ 的六类置换多项式的逆）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：置换多项式（Permutation Polynomials, PPs）在有限域上的研究已有百年历史，近年来在密码学（如 AES 算法中的 S 盒设计）、公钥密码体制和编码理论中扮演着关键角色。
核心问题：虽然置换多项式的存在性由其双射性质保证，但**显式地计算其复合逆（Compositional Inverse）**是一个极具挑战性的代数问题。传统的拉格朗日插值法虽然理论上可行，但通常会产生包含所有可能项的复杂多项式，缺乏代数结构洞察且计算成本高昂。
具体对象：本文聚焦于 Jiang 等人 [21] 近期提出的六类特定形式的置换多项式，其定义在偶特征有限域 $\mathbb{F}_{q^2}$ （其中 $q=2^m$ ）上，形式为：
$f(x) = x + \gamma \text{Tr}_{q^2}^q(h(x))$
其中 $\text{Tr}_{q^2}^q$ 是从 $\mathbb{F}_{q^2}$ 到 $\mathbb{F}_q$ 的迹函数， $\gamma \in \mathbb{F}_{q^2}$ ， $h(x)$ 为特定的多项式。
目标：为这六类置换多项式推导其显式的复合逆多项式 $f^{-1}(x)$ 。

2. 方法论 (Methodology)

本文采用了一种基于线性化多项式分解和基变换的代数构造方法，主要步骤如下：

辅助引理构建：
- 利用 $\mathbb{F}_{q^2}$ 在 $\mathbb{F}_q$ 上的基 $\{1, \alpha\}$ （其中 $\text{Tr}_{q^2}^q(\alpha)=1$ ），将问题转化为线性方程组求解。
- 引理 2.3：构造了一个辅助置换多项式 $T(x) = \text{Tr}_{q^2}^q(\beta x) + \alpha \text{Tr}_{q^2}^q(\delta x)$ ，并给出了其逆 $T^{-1}(x)$ 的显式公式。这是整个推导的核心工具。
- 引理 2.4：建立了 $T^{-1}$ 与迹函数之间的特定关系，用于简化后续计算。
共轭变换法（Conjugation Method）：
- 对于目标多项式 $f(x)$ ，作者构造辅助映射 $T(x)$ （或 $U(x)$ ），计算复合函数 $f \circ T(x)$ 。
- 通过比较系数，将 $f \circ T(x) = T(y)$ 转化为关于迹函数的线性方程组或可解的非线性方程组。
- 利用矩阵行变换（Elementary Row Operations）求解 $x$ 关于 $y$ 的表达式，从而得到 $T^{-1} \circ f^{-1} \circ T$ 的形式。
- 最后，通过 $f^{-1}(x) = \text{Tr}_{q^2}^q[\beta(T^{-1} \circ f^{-1}(x))] + \alpha \text{Tr}_{q^2}^q[\delta(T^{-1} \circ f^{-1}(x))]$ 还原出 $f^{-1}(x)$ 的显式表达式。
分情况讨论：
- 根据参数 $\gamma$ 的取值（属于 $\mathbb{F}_q$ 或 $\mathbb{F}_{q^2} \setminus \mathbb{F}_q$ ）以及 $m$ 的奇偶性，采用不同的基和逆映射策略。
- 对于涉及 $x^3$ 的项，利用引理 2.1（当 $m$ 为奇数时， $x^3$ 是置换多项式），引入指数 $t$ 满足 $3t \equiv 1 \pmod{2^m-1}$ 来求逆。

3. 主要结果 (Key Contributions & Results)

论文成功推导了六类置换多项式的复合逆，具体结果如下（设 $q=2^m$ ）：

$f_1(x) = x + \gamma \text{Tr}_{q^2}^q(x^3 + x^{q+2})$
- 条件： $\gamma \in \mathbb{F}_q$ 。
- 逆： $f_1^{-1}(x) = x + \gamma (\text{Tr}_{q^2}^q(x))^3$ 。
- 特点：逆多项式形式极其简洁，仅涉及迹函数的立方。
$f_2(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^2 + x^3 + x^{q+2})$
- 条件： $\gamma \in \mathbb{F}_q$ 。
- 逆： $f_2^{-1}(x) = x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$ 。
- 特点：逆多项式是迹函数的线性组合及其幂次和。
$f_3(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^3 + x^{q+2})$
- 情况 A：若 $\gamma \in \mathbb{F}_q$ ，则 $f_3^{-1}(x) = x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^3$ 。
- 情况 B：若 $\text{Tr}_{q^2}^q(\gamma) = 1$ 且 $m$ 为奇数，则 $f_3^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma (\text{Tr}_{q^2}^q(x))^t$ ，其中 $3t \equiv 1 \pmod{2^m-1}$ 。
$f_4(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^3 + x^{q+2})$
- 情况 A：若 $\gamma \in \mathbb{F}_q$ ，则 $f_4^{-1}(x) = x + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$ 。
- 情况 B：若 $\text{Tr}_{q^2}^q(\gamma) = 1$ 且 $m$ 为奇数，则 $f_4^{-1}(x) = \text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [(\text{Tr}_{q^2}^q(x) + 1)^t + 1]$ 。
$f_5(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^{q+2})$
- 条件： $m$ 为奇数， $\gamma \in \mathbb{F}_{2^2} \setminus \{1\}$ （即 $\gamma^2+\gamma+1=0$ ）。
- 逆：给出了一个包含 $t$ 次幂的复杂表达式，涉及 $\text{Tr}_{q^2}^q(x)$ 和 $\text{Tr}_{q^2}^q((1+\gamma)x)$ 的组合。
$f_6(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^{q+2})$
- 条件： $m$ 为奇数， $\gamma \in \mathbb{F}_{2^2} \setminus \{1\}$ 。
- 逆：同样给出了显式表达式，形式为 $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [\dots]$ ，其中包含 $t$ 次幂运算。

4. 意义与价值 (Significance)

理论贡献：
- 解决了 Jiang 等人 [21] 提出的六类特定置换多项式的逆问题，填补了该领域显式逆公式的空白。
- 展示了如何利用迹函数的性质和基变换技巧，将复杂的非线性置换多项式逆问题转化为可解的线性或低次非线性系统。
- 证明了在特定条件下（如 $m$ 为奇数），涉及 $x^3$ 的项可以通过指数 $t$ 进行显式求逆，丰富了有限域上置换多项式的构造理论。
应用价值：
- 密码学：在分组密码（如 AES）和流密码设计中，S 盒通常由置换多项式构造。显式的逆多项式对于实现解密过程、进行差分分析和线性分析至关重要。本文提供的简洁逆公式（特别是 $f_1, f_2$ 等）可以直接用于设计具有良好代数结构且易于实现的 S 盒。
- 编码理论：置换多项式在构造纠错码（如 Reed-Solomon 码的变体）和序列设计中具有应用，其逆多项式有助于解码算法的设计。

5. 总结

该论文通过严谨的代数推导，利用辅助线性映射和迹函数的性质，成功获得了六类偶特征有限域上置换多项式的显式复合逆。这些结果不仅形式简洁（多为迹函数的多项式组合），而且具有明确的代数结构，为密码学和编码理论中的实际应用提供了重要的理论工具。特别是对于 $m$ 为奇数的情况，论文巧妙地利用了 $x^3$ 的置换性质，给出了包含高次幂项的逆公式，展示了该领域研究的深度。