寻找有限域同构映射

本文主要是介绍寻找有限域同构映射，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、有限域简介

有限域亦称伽罗瓦域（Galois Fields），是伽罗瓦于 18 世纪 30 年代研究代数方程根式求解问题时引出的概念。有限域在密码学、近代编码、计算机理论、组合数学等方面有着广泛的应用

在抽象代数中，域是一个对加法和乘法封闭的集合，其中要求每个元素都有加法逆元，每个非零元素都有乘法逆元。若域 \(F\) 只包含有限个元素，则称为有限域，有限域中元素的个数称为有限域的阶。可以证明，有限域的阶必为素数的幂，即有限域的阶可表示为 \(p^n\)（\(p\) 是素数，\(n\) 是正整数）。有限域通常记为 \(GF(p^n)\)

二、有限域同构

因为网上似乎都没有如何寻找有限域同构映射的资料，而正好我上课学到了相关的内容，在此结合自己的理解作简单的介绍。因为不是数学系相关的学生，而且对有限域的理解仅处于皮毛，有很多定理没办法给出详细的证明，在逻辑上或许会多有漏洞，如果读者发现我的漏洞希望能够指出。
（虽然指出了我也不一定能听懂，但还是希望能够指出）

另外，有限域的相关知识（例如有限域的性质，有限域的构造等）将默认读者已经了解，在阅读后续内容前先保证对上述知识有所了解

2.1 寻找同构映射思路

首先，任意相同阶数的有限域都同构。假设 \(p(x)\) 和 \(q(x)\) 都是域 \(F_p\) 上的 \(n\) 阶不可约多项式，那么有限域 \(F_1 = F_p[x] / p(x)\) 和 \(F_2 = F_p[x] / q(x)\) 都是 \(p^n\) 阶有限域。

有下面两条重要定理：

如果假设 \(\alpha\) 是多项式 \(p(x)\) 的一个根，那么有限域 \(F_1\) 可以表示成 \(F_p[\alpha]\)
如果假设 \(\beta\) 是多项式 \(q(x)\) 的一个根，那么有限域 \(F_2\) 可以表示成 \(F_p[\beta]\)

现在需要找到一个两者的同构映射 \(\phi\)
首先，根 \(\alpha\) 和 \(\beta\) 满足 \(p(\alpha)=0\) 和 \(q(\beta)=0\)
直接将 \(\alpha\) 映射到 \(\beta\) 是不可行的，因为线性关系无法保证，即无法保证 \(p(\beta)=0\)
那么如果找到 \(\beta ' \in F_p[\beta]\) 使得 \(p(\beta')=0\) 成立，这样就可以构造 \(\alpha \to \beta '\) 的映射

2.2 寻找同构映射例子

求有限域 \(Z_3[x] / (x^2 + 1)\) 和 \(Z_3[x] / (x^2 + x +2)\) 之间的同构映射

记 \(p(x) = x^2 + 1\) ，\(q(x) = x^2 + x + 2\)
且有 \(\alpha = \overline{x} \; mod \; p(x)\) 为 \(p(x)\) 的一个根
且有 \(\beta = \overline{x} \; mod \; q(x)\) 为 \(q(x)\) 的一个根

寻找得到 \(\beta' = \beta + 2\) ，使得 \(p(\beta') = (\beta + 2)^2 + 1 = \beta^2 + \beta + 2 = 0\)
那么对应的映射为 \(\alpha \to \beta + 2\)

也就是原先 \(Z_3[\alpha]\) 中的元素 \(a_1 \alpha + a_0\) 将被映射成 \(a_1 (\beta + 2) + a_0 = a_1 \beta + (2a_1 + a_0) \in Z_3[\beta]\)
或者说原先 \(Z_3[x] / (x^2 + 1)\) 中的元素 \(a_1 x + a_0\) 将被映射到 \(Z_3[x] / (x^2 + x +2)\) 中的 \(a_1 x + (2a_1 + a_0)\)

2.3 同构映射逆映射

在 2.2 中已经求出了一个同构映射 \(\alpha \to \beta + 2\)
很容易发现 \(q(\alpha - 2) = (\alpha - 2)^2 + (\alpha - 2) + 2 = \alpha^2 + 1 = 0\)

也就是说逆映射为 \(\beta \to \alpha - 2\)

三、复合域与同构

3.1 复合域

接下来介绍一个稍微复杂的有限域——复合域，复合域在密码学中具有非常大的用途，将一个高阶的有限域转化为两个或多个低阶有限域的复合，便于后续分析

记 \(p(x) = x^2 + x + 4\) ，\(F_2[x] / p(x)\) 为 \(2^2\) 阶有限域
记 \(q(x) = x^4 + x^3 + 1\) ，\(F_2[x] / q(x)\)为 \(2^4\) 阶有限域
那么将两者复合得到 \(F : b_1 x + b_2 \; mod \; p(x), \; b_i \in F_2[x] / q(x)\) ，为 \((2^4)^2 = 2^8\) 阶有限域（复合域）

3.2 复合域同构

通过一个例子来了解求复合域同构的过程

记 \(F_2[x] / r(x)\) 为 \(2^8\) 阶有限域， \(r(x) = x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1\)

记 \(F[x] / (p(x), q(y)) = (a_3 y^3 + a_2 y^2 + a_1 y + a_0) x + (b_3 y^3 + b_2 y^2 + b_1 y + b_0)\) 为上述 3.1 中的 \((2^4)^2\) 阶有限域

求 \(F_2[x] / r(x) \to F[x] / (p(x), q(x))\) 的一个同构映射

首先，需要遍历 \(F[x] / (p(x), q(y))\) 的全部元素，找到其中一个 \(\beta'\) 满足 \(r(\beta') = 0\) 的元素 \((y^2 + 1)x + (y^3 + y^2 + y)\)
记 \(\alpha = \overline{x} \; mod \; r(x)\) 为 \(r(x)\) 的根
那么同构映射为 \(\alpha \to \beta'\)

四、映射矩阵

4.1 有限域与矩阵

在密码学中，常将多项式表示为矩阵的形式，例如在 \(GF(2^8)\) 上的多项式

\[x^7 + x^6 + x + 1 \equiv \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}^T \]

假设 \(p(x)\) 和 \(q(x)\) 都是 \(F_2\) 上的 \(8\) 次不可约多项式，那么可以构成 \(2^8\) 阶有限域 \(F_2[x]/p(x)\) 和 \(F_2[x]/q(x)\)

假设 \(\alpha\) 是多项式 \(p(x)\) 的一个根，那么有限域 \(F_2[x]/p(x)\) 可以表示成 \(F_2[\alpha]\)
假设 \(\beta\) 是多项式 \(q(x)\) 的一个根，那么有限域 \(F_2[x]/q(x)\) 可以表示成 \(F_2[\beta]\)

且假设 \(c_7 x^7 + c_6 x^6 + c_5 x^5 + \cdots + c_1 x + c_0\) 是 \(F_2[x]/p(x)\) 上的一个多项式，那么该多项式也可以等价于 \(c_7 \alpha^7 + c_6 \alpha^6 + c_5 \alpha^5 \cdots c_1 \alpha + c_0\) ,即

\[\begin{bmatrix} \alpha^7 & \alpha^6 & \alpha^5 & \alpha^4 & \alpha^3 & \alpha^2 & \alpha & 1 \end{bmatrix} \times \begin{bmatrix} c_7 & c_6 & c_5 & c_4 & c_3 & c_2 & c_1 & c_0\end{bmatrix}^T \]

4.2 多项式矩阵

假设 \(\alpha^i = a_{7,i} x^7 + a_{6,i} x^6 + \cdots a_{1,i} x + a_{0,i}\)

那么

\[\begin{bmatrix} \alpha^7 \\ \alpha^6 \\ \alpha^5 \\ \alpha^4 \\ \alpha^3 \\ \alpha^2 \\ \alpha \\ 1 \end{bmatrix}^T \equiv \begin{bmatrix} a_{7,7} & a_{7,6} & a_{7,5} & a_{7,4} & a_{7,3} & a_{7,2} & a_{7,1} & a_{7,0}\\ a_{6,7} & a_{6,6} & a_{6,5} & a_{6,4} & a_{6,3} & a_{6,2} & a_{6,1} & a_{6,0}\\ a_{5,7} & a_{5,6} & a_{5,5} & a_{5,4} & a_{5,3} & a_{5,2} & a_{5,1} & a_{5,0}\\ a_{4,7} & a_{4,6} & a_{4,5} & a_{4,4} & a_{4,3} & a_{4,2} & a_{4,1} & a_{4,0}\\ a_{3,7} & a_{3,6} & a_{3,5} & a_{3,4} & a_{3,3} & a_{3,2} & a_{3,1} & a_{3,0}\\ a_{2,7} & a_{2,6} & a_{2,5} & a_{2,4} & a_{2,3} & a_{2,2} & a_{2,1} & a_{2,0}\\ a_{1,7} & a_{1,6} & a_{1,5} & a_{1,4} & a_{1,3} & a_{1,2} & a_{1,1} & a_{1,0}\\ a_{0,7} & a_{0,6} & a_{0,5} & a_{0,4} & a_{0,3} & a_{0,2} & a_{0,1} & a_{0,0} \end{bmatrix} \]

当 \(\alpha = \overline{x} \; mod \; p(x)\) 时，上式为单位阵 \(I\)

4.3 同构映射与矩阵

假设 \(c_7 x^7 + c_6 x^6 + c_5 x^5 + \cdots + c_1 x + c_0\) 是 \(F_2[x]/p(x)\) 上的多项式
假设 \(d_7 x^7 + d_6 x^6 + d_5 x^5 + \cdots + d_1 x + d_0\) 是 \(F_2[x]/q(x)\) 上的多项式

记它们两者的矩阵表示为 \(C\) 和 \(D\)

要找到两个域的映射关系，将一个多项式映射到另一个多项式
也就是要找到一个映射矩阵 \(T\) ，使得一个多项式的矩阵表示 \(C\) 和另一个多项式的矩阵表示 \(D\) 满足 \(TC = D\)

上文提到，可以找到一个同构映射 \(\alpha \to \beta'\) ，使得有限域 \(F_2[\alpha]\) 和有限域 \(F_2[\beta]\) 同构

根据同构关系的线性性质，有 \(\alpha^i \to \beta'^i\) ，故映射为

\[c_7 \alpha^7 + c_6 \alpha^6 + c_5 \alpha^5 \cdots c_1 \alpha + c_0 \to c_7 \beta'^7 + c_6 \beta'^6 + c_5 \beta'^5 \cdots c_1 \beta' + c_0 \]

记 \(\alpha\) 对应的矩阵（如4.2所示）为 \(A\) ， \(\beta'\) 对应的矩阵为 \(B\)
那么映射矩阵 \(T\) 满足 \(TAC = BC\) ，即 \(T= B A^{-1}\)

为了计算方便，一般选取的根 \(\alpha = \overline{x} \; mod \; p(x)\)
那么 \(\alpha\) 对应的矩阵 \(A\) 即为单位阵 \(I\)
那么 \(T = B\)

假设 \(\beta'^i = b_{7,i} x^7 + b_{6,i} x^6 + \cdots b_{1,i} x + b_{0,i}\)
那么

\[T = \begin{bmatrix} b_{7,7} & b_{7,6} & b_{7,5} & b_{7,4} & b_{7,3} & b_{7,2} & b_{7,1} & b_{7,0}\\ b_{6,7} & b_{6,6} & b_{6,5} & b_{6,4} & b_{6,3} & b_{6,2} & b_{6,1} & b_{6,0}\\ b_{5,7} & b_{5,6} & b_{5,5} & b_{5,4} & b_{5,3} & b_{5,2} & b_{5,1} & b_{5,0}\\ b_{4,7} & b_{4,6} & b_{4,5} & b_{4,4} & b_{4,3} & b_{4,2} & b_{4,1} & b_{4,0}\\ b_{3,7} & b_{3,6} & b_{3,5} & b_{3,4} & b_{3,3} & b_{3,2} & b_{3,1} & b_{3,0}\\ b_{2,7} & b_{2,6} & b_{2,5} & b_{2,4} & b_{2,3} & b_{2,2} & b_{2,1} & b_{2,0}\\ b_{1,7} & b_{1,6} & b_{1,5} & b_{1,4} & b_{1,3} & b_{1,2} & b_{1,1} & b_{1,0}\\ b_{0,7} & b_{0,6} & b_{0,5} & b_{0,4} & b_{0,3} & b_{0,2} & b_{0,1} & b_{0,0} \end{bmatrix} \]

4.4 一般算法流程

首先，需要找到两个域 \(F_2[x]/p(x)\) 和 \(F_2[x]/q(x)\) 满足映射关系的 \(\alpha\) 和 \(\beta'\)
其中 \(\alpha = \overline{x} \; mod \; p(x)\) ， \(\beta = \overline{x} \; mod \; q(x)\)
且 \(p(\beta') = 0, \beta' \in F_2[\beta] = F_2[x]/q(x)\)

计算 \(\beta'^i, i = 0, 1, \cdots , 7\) ，并将 \(\beta'^i\) 的系数值置于矩阵 \(T\) 的倒数第 \(i\) 列（从0开始）

五、代码实现（寻找同构映射）

有限域的四则运算：点击此处跳转

假设 \(p(x) = x^8 + x^4 + x^3 + x + 1\) ，\(q(x) = x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1\)
需要求解 \(F_2[x]/p(x)\) 和 \(F_2[x]/q(x)\) 之间的映射关系

5.1 有限域类(GF2⁸)

def gf2_mul(a: int, b: int, poly: int) -> int:
    """有限域乘法"""
    ans = 0
    digit = poly.bit_length() - 1
    while b:
        if b & 1:
            ans = ans ^ a
        a, b = a << 1, b >> 1
        if a >> digit:
            a = a ^ poly
    return ans


class GF256:
    def __init__(self, value, poly):
        self.value = value
        self.poly = poly

    def __add__(self, other):
        """加法"""
        return GF256(self.value ^ other.value, self.poly)

    def __sub__(self, other):
        """减法"""
        return GF256(self.value ^ other.value, self.poly)

    def __mul__(self, other):
        """乘法"""
        return GF256(gf2_mul(self.value, other.value, self.poly), self.poly)

    def __pow__(self, power, modulo=None):
        """幂"""
        res = GF256(1, self.poly)
        for i in range(power):
            res = res * self
        return res

5.2 p(x)和q(x)定义

px = 0b100011011  # x^8 + x^4 + x^3 + x + 1
qx = 0b111110101  # x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
p = lambda x: x ** 8 + x ** 4 + x ** 3 + x + x ** 0
q = lambda x: x ** 8 + x ** 7 + x ** 6 + x ** 5 + x ** 4 + x ** 2 + x ** 0

5.3 遍历搜索

for i in range(2 ** 8):
    # 遍历 F_2[x]/q(x) 的元素
    t = GF256(i, qx)
    if p(t).value == 0:  # 满足p(t)=0
        print(bin(t.value))

得到8个结果

5.4 结果

令 \(\alpha = \overline{x} \; mod \; p(x)\) 为 \(p(x)\) 的一个根
令 \(\beta = \overline{x} \; mod \; q(x)\) 为 \(q(x)\) 的一个根

上述结果也就是找到了8个映射关系，分别为

值	关系
0b100000	\(\alpha \to \beta^5\)
0b110011	\(\alpha \to \beta^5 + \beta^4 + \beta + \beta^0\)
0b111110	\(\alpha \to \beta^5 + \beta^4 + \beta^3 + \beta^2 + \beta^1\)
0b1110000	\(\alpha \to \beta^6 + \beta^5 + \beta^4\)
0b10011111	\(\alpha \to \beta^7 + \beta^4 + \beta^3 + \beta^2 + \beta^1 + \beta^0\)
0b10100110	\(\alpha \to \beta^7 + \beta^5 + \beta^2 + \beta^1\)
0b10101010	\(\alpha \to \beta^7 + \beta^5 + \beta^3 + \beta^1\)
0b11001110	\(\alpha \to \beta^7 + \beta^6 + \beta^3 + \beta^2 + \beta^1\)

六、有限域同构与密码学

在例如 AES 和 SM4 这类对称密码的 S 盒变换的底层，所使用的就是有限域 \(GF(2^8)\) 的求逆变换（除了求逆还涉及一些仿射变换）。

如果采用硬件（例如FPGA）实现密码算法，可将 \(GF(2^8)\) 的同构于 \(GF((2^4)^2)\) 复合域甚至同构于 \(GF(((2^2)^2)^2)\) 复合域，便于分析有限域的求逆表达式，使用逻辑函数代替原先的查表运算，能够节省门电路资源

如果使用软件实现，可以利用有限域同构关系将 SM4 的 S盒转化为 AES 的 S盒，利用 AES 指令集完成 SM4 的 S盒操作

这篇关于寻找有限域同构映射的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

寻找有限域同构映射

一、有限域简介

二、有限域同构

2.1 寻找同构映射思路

2.2 寻找同构映射例子

2.3 同构映射逆映射

三、复合域与同构

3.1 复合域

3.2 复合域同构

四、映射矩阵

4.1 有限域与矩阵

4.2 多项式矩阵

4.3 同构映射与矩阵

4.4 一般算法流程

五、代码实现（寻找同构映射）

5.1 有限域类(GF2⁸)

5.2 p(x)和q(x)定义

5.3 遍历搜索

5.4 结果

六、有限域同构与密码学

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

寻找有限域同构映射

一、有限域简介

二、有限域同构

2.1 寻找同构映射思路

2.2 寻找同构映射例子

2.3 同构映射逆映射

三、复合域与同构

3.1 复合域

3.2 复合域同构

四、映射矩阵

4.1 有限域与矩阵

4.2 多项式矩阵

4.3 同构映射与矩阵

4.4 一般算法流程

五、代码实现（寻找同构映射）

5.1 有限域类(GF28)

5.2 p(x)和q(x)定义

5.3 遍历搜索

5.4 结果

六、有限域同构与密码学

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

5.1 有限域类(GF2⁸)