Matrix_Branch and MDS

有限域 $(G F (P))$

??为什么要写有限域??

关于离散数学和有限域的概念可参考：另一种世界观——有限域

对以下需要用到的有限域知识作简要介绍，以最常见的对模素数 p 为例：

$(G F (P)) 有限域又叫做伽罗瓦域，该域仅包含有限个元素，其对加减乘除都有规则性定义（当然不同于我们之前对四则运算的理解）$

$(G F (P)) 的阶（有限域中元素的个数）是一个素数 p 的幂，对模 p 的有限域其阶数为 p - 1. 同时 p 称为域的 < f o n t c o l o r = r e d > 生成元 < / f o n t > .$

$由于每次运算都在模 p 下进行，所以域中元素限制在 0 (p - 1) 内 .$

$有限域首先要是域；域要求是成除环和交换环；除环要求幺半群全体元素带乘法逆元，交换环要求乘法群对乘法满足交换律；幺半群在半群的基础上存在单位元（幺元），群在幺半群的基础上又要求每个元素存在逆元；半群是对元素运算法则满足 “ 封闭性 ” 和 “ 结合律 ” 的集合。（这里的加法和乘法不同于四则运算）$

小记：区别生成元和本原元（或本原根，原根）
对模 19 下 7 的阶作考量： $7^{1} = 7 m o d 19, 7^{2} = 11 m o d 19, 7^{3} = 1 m o d 19, 7^{4} = 7 m o d 19...$
可以发现没 3 次模幂数运算就进入循环，则模 19 下 7 的阶为 3（这和上面的定义并不冲突）

$给出定义：若\,模 n 下 a 的阶为 d = \varphi(n),\varphi(n) 是 n 的欧拉函数::$

$a 称作 n 的本原元（模 n 达到满阶）$

$同时 a 也是 Z_{n}^{*} 的生成元（可由 a 构成 Z_{n}^{*} 的全体元素） .$

矩阵的分支数 $(The\;number\;of\;Branches\;of\;the\;matrix)$

在 Rijndael 的定义文章中，给出了其在线形成变换使用矩阵的最大分支数，对 m 阶的矩阵，该分支数达到了最大。

alt

解释：
这里的向量是面向 byte 的，但是可以看作 nonzero = 1；zero = 0

其中 a 是 m 维的列向量，W(a)是向量 a 的重量，即向量 a 中非零元素的个数（注意并不是广义上的汉明重量）；
F 是定义的线性变换，可以看作一个 m * m 的矩阵右乘一个 m * 1 的列向量（即 a 向量）：(Eg)

\begin{gathered} \begin{pmatrix} 1 & 0 &1 & 0\\ 0 & 1 & 0 & 0 \\0 & 0 & 1 & 0\\1 & 0 & 0 & 1\end{pmatrix} \quad * \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0\end{pmatrix} \end{gathered}

若要求式 $min_(a \neq 0)(W(a) + W(F(a)))$ 取到最大值，则 $W (F (a))$ 要取到最大值，即线性变换要求能够产生最大扩散，而取最小时 $W (a) = 1$ ，所以 F 必须对所以可能的 a （这里可以理解为 $a = [a_{1}, a_{2}, a_{3}, a_{4}]^{T}$ ，其中各个元素均为 0 或 1.）都能求出含有 4 个非零元素的列向量。即最大的分支数只能为 $m + 1$

而能够达到该要求的矩阵，就称作 $MDS\;matrix(Maximum\;Distance\;Separable)$

当然，MDS 矩阵还有很多性质（或要求）：

要求，可以对任何非全零输入达到最大扩散（即每一byte影响多个byte）；
矩阵本身和其小于其阶数的各阶子矩阵都是非奇异矩阵；
如果它是从域 $K^{n}$ 到 $K^{m}$ 的线性变换 $f (x) = A x$ 的变换矩阵，使得没有两个不同的 $(m + n) - (x, f (x))$ 形式的元组在 $n$ 个或更多分量中重合。(可以理解为，在域上的不同输入不会产生输出碰撞_I Don`t Know）

很多密码，如 $AES、SHARK、Square、Twofish、Manta、Hierocrypt\;and\;Camellia$ 的线形层都使用了 $MDS\;matrix$ .

Matrix_Branch and MDS

有限域 (GF(P))(GF(P))(GF(P))

矩阵的分支数(The number of Branches of the matrix)(The\;number\;of\;Branches\;of\;the\;matrix)(ThenumberofBranchesofthematrix)

有限域 $(G F (P))$

矩阵的分支数 $(The\;number\;of\;Branches\;of\;the\;matrix)$