🔢 mathematics

On the generalization of $g$ -circulant MDS matrices

本文通过引入一种基于多项式线性变换的新型“常数- $g$ -循环矩阵”（consta- $g$ -circulant matrix），研究了其可逆性条件、可逆矩阵的数量公式，并给出了3阶和4阶 $g$ -循环MDS矩阵的完整特征描述及新变体的构造。

原作者： Atif Ahmad Khan, Shakir Ali, Bhupendra Singh

发布于 2026-02-11

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Atif Ahmad Khan, Shakir Ali, Bhupendra Singh

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

这是一篇关于数学和密码学的高深论文。为了让你听懂，我们不需要去啃那些复杂的公式，而是要把这些矩阵想象成一种**“超级信息搅拌机”**。

1. 背景：为什么要研究这个？（“信息搅拌机”的重要性）

想象你在做一个极其机密的“秘密汤”。如果你只是把盐、胡椒和肉丢进去，别人一眼就能看出里面有什么。在密码学（比如保护你银行卡密码的技术）中，我们需要一种方法，把原始信息（明文）和密钥（Key）混合得极其均匀，让黑客哪怕拿到了部分信息，也完全无法推断出原貌。

这种“搅拌”的过程就叫**“扩散”（Diffusion）。而论文里提到的 MDS 矩阵，就是这种搅拌机的“顶级配置”**。

什么是 MDS 矩阵？ 想象一个搅拌机，如果你只往里加了一小勺盐，它也能让整锅汤的味道瞬间改变。MDS 矩阵的特性就是：哪怕你只改变了输入信息中的一个微小字节，输出的结果也会发生翻天覆地的变化。 这种“牵一发而动全身”的特性，让它成为了密码学防御黑客的最佳工具。

2. 核心挑战：效率与性能（“搅拌机”的体积问题）

虽然 MDS 矩阵很强，但它有一个致命缺点：太占地方了！

一个普通的 $m \times m$ 矩阵需要存储 $m^2$ 个数字。如果矩阵很大，计算起来就会非常慢，手机或芯片的内存也会吃不消。

科学家们一直在寻找一种**“精简版”**的 MDS 矩阵——即：只需要记住一小部分参数，就能通过某种规律“变”出整个大矩阵。 这就像你不需要背下整本菜谱，只需要记住一个“核心公式”，就能变出整桌满汉全席。

3. 论文的新发现：Consta-g-circulant 矩阵（“魔法公式”的升级版）

这篇论文的核心贡献，就是发明了一种新型的“精简公式”，作者管它叫 “Consta-g-circulant 矩阵”。

我们可以用**“旋转木马”**来做类比：

普通的 Circulant 矩阵（循环矩阵）： 就像一个旋转木马，每一排的乘客位置都只是上一排乘客向右挪了一个位。非常规律，非常省空间。
g-circulant 矩阵： 升级版旋转木马。每一排不仅在转，而且转动的步长（g）不一样，可能一次跳两格，或者跳三格。
本文的 Consta-g-circulant 矩阵（新发明）： 这是**“带魔法加成的旋转木马”**。在旋转的同时，每一圈还会根据一个特殊的系数（ $\lambda$ ）进行一次“变身”或“缩放”。

这篇论文做了三件大事：

给出了“说明书”： 作者通过数学证明，告诉大家这种新型“旋转木马”在什么条件下是可逆的（即：搅拌完之后，我们还能通过数学手段把汤还原成食材，这对于解密至关重要）。
算出了“库存量”： 作者给出了一个公式，可以直接算出这种矩阵到底有多少种组合方式。这就像是在问：“世界上到底有多少种不同的魔法旋转木马组合？”
找到了“完美组合”： 作者不仅研究了这种矩阵，还研究了它的“镜像版”（Involutory，即搅拌一次和反向搅拌一次的效果是一样的），这能让加密和解密的速度变得极快。

4. 总结：这有什么用？

简单来说，这篇论文为未来的网络安全提供了一套**“更轻量、更强大、更聪明”**的数学工具。

更轻量： 以后你的手机在处理复杂的加密任务时，不需要消耗巨大的内存和电量，因为“搅拌机”的参数变少了。
更强大： 这种新型矩阵提供了更复杂的数学结构（通过引入“偏斜多项式环”等概念），让黑客更难通过数学规律去破解。

一句话总结：
作者发明了一种更高级的“数学搅拌公式”，让我们的信息加密既能像“超级搅拌机”一样搅得密不透风，又能像“轻量化工具”一样运行得飞快。

这是一篇关于代数编码理论与密码学中矩阵构造的研究论文。以下是对该论文的详细技术总结：

1. 研究问题 (Problem)

在对称加密算法（如 AES）的扩散层设计中，最大距离可分矩阵 (MDS Matrix) 至关重要，因为它们能提供最优的扩散特性。为了降低硬件和软件实现的复杂度，研究人员通常寻求具有特殊结构的矩阵，如循环矩阵 (Circulant matrices) 或 $g$ -循环矩阵 ( $g$ -circulant matrices)。

然而，传统的循环矩阵在某些条件下（如特征为 2 的有限域上）存在结构性限制，无法构造出某些理想性质的矩阵（如对合矩阵/Involutory matrices）。本文旨在通过推广现有概念，寻找能够突破这些限制、同时保持高效实现特性的新型 MDS 矩阵结构。

2. 研究方法 (Methodology)

本文的核心方法是引入并研究一种全新的矩阵类：Consta- $g$ -循环矩阵 (Consta- $g$ -circulant matrices)。

数学定义：基于有限域 $\mathbb{F}_q$ 上的多项式环 $\mathbb{F}_q[x]/(x^m - \lambda)$ 。通过一个线性变换 $\phi(\bar{Q}(x)) = \bar{Q}(x^g)\bar{h}(x)$ 来定义。其中 $\lambda \in \mathbb{F}_q^*$ 是一个非零常数，它改变了传统的行移位机制。
推广路径：
1. 当 $\lambda=1, g=1$ 时，退化为循环矩阵。
2. 当 $\lambda=1$ 时，退化为 $g$ -循环矩阵。
3. 进一步引入域自同构 $\theta$ ，构造了 Consta- $\theta g$ -循环矩阵，利用斜多项式环 (Skew polynomial rings) $\mathbb{F}_q[X; \theta]$ 进行理论分析。
分析工具：利用中国剩余定理 (CRT) 进行计数，利用汉明重量 (Hamming weight) 的性质来刻画 MDS 性质，并利用哈达玛积 (Hadamard product) 研究矩阵性质在特征为 2 的域下的稳定性。

3. 核心贡献 (Key Contributions)

定义新概念：首次提出了 Consta- $g$ -循环矩阵 及其在斜多项式环下的变体 Consta- $\theta g$ -循环矩阵。
计数理论：推导出了此类矩阵的可逆性条件，并给出了可逆 Consta- $g$ -循环矩阵数量的精确计算公式。
性质刻画：给出了此类矩阵成为 MDS 矩阵 和 对合矩阵 (Involutory matrices) 的充分必要条件。
算法实现：针对阶数为 3 和 4 的 $g$ -循环 MDS 矩阵，设计了基于权重的搜索算法。
结构稳定性证明：证明了在特征为 2 的域中，通过哈达玛幂运算（Hadamard power）可以保持矩阵的 MDS、对合及半对合性质。

4. 主要结果 (Results)

数量界限与计数：证明了 Consta- $g$ -循环矩阵的总数上限，并给出了可逆矩阵的数量公式： $N \cdot \prod_{i=1}^{t} (q^{\deg f_i} - 1)$ ，其中 $f_i$ 是 $x^m - \lambda$ 的不可约因子。这极大地缩小了寻找加密用 MDS 矩阵的搜索空间。
MDS 与对合性的判定：
- 对于 $3 \times 3$ 矩阵，判定条件简化为：关联多项式 $h(x)$ 及其逆 $h^{-1}(x)$ 的汉明重量均为 3。
- 对于对合 MDS 矩阵，给出了基于多项式乘法模 $x^m - \lambda$ 的判定准则。
突破限制：通过实例（Example 3 & 4）证明，Consta- $\theta g$ -循环矩阵可以构造出传统循环矩阵无法构造的、具有 MDS 性质的对合矩阵。
性质保持：证明了若 $A$ 是 $\theta g$ -循环矩阵，则其对应的哈达玛 $2^s$ 次幂矩阵在 MDS 和对合性上与原矩阵等价。

5. 研究意义 (Significance)

密码学应用：本文的研究成果直接服务于对称加密算法（如分组密码）的扩散层设计。新构造的矩阵既具有 MDS 带来的强扩散性，又具有循环结构带来的低存储成本和高效实现能力。
理论价值：将 Constacyclic codes（常循环码）的思想扩展到 $g$ -循环矩阵领域，并成功结合了斜多项式环理论，为构造具有特殊代数性质的矩阵提供了新的数学框架。
工程实用性：通过提供的计数公式和搜索算法，研究人员可以快速、精确地在有限域内筛选出符合特定安全要求的扩散矩阵，避免了盲目的穷举搜索。