密码学基础——GF（2）有限域上的矩阵求逆

密码学基础——GF（2）有限域上的矩阵求逆"/>

密码学基础——GF（2）有限域上的矩阵求逆

文章目录

• 前言
• 数据结构
• 随机生成GF（2）上4X4的矩阵
• 判断GF（2）上有限域矩阵是否可逆
• 求GF（2）上有限域矩阵的可逆矩阵

前言

上篇文章介绍了实数域上的线性代数求解可逆矩阵的方法，但有时候我们有更复杂的需求，如在有限域上求解可逆矩阵，有限域是一个很有意思的东西，它的知识可见这篇文章
今天我们简单描述如何在GF（2）有限域上求解4X4矩阵的可逆矩阵。

数据结构

总所周知，GF（2）上的加法和乘法可以分别用异或（^）和逻辑与(&)来表示，因此，我们可以将矩阵中的每一行都可以被定义为一个数字，而不是一个二进制数组。这样做除了内存成本外，运行也会更高效。因为行上的操作比列上的操作更快，例如，两个8位向量之间的乘法（即，向量的内乘）需要GF（2）域上的8次乘法和7次加法。但是如果两个向量定义为单字节数字，则部分乘法的运算将减少为1个逻辑与。类似地，向量加法也可以减少为1个异或操作。
在C语言中我们使用结构体来定义4x4矩阵，我们将矩阵每一行看作一个数，那么实现代码如下：

typedef unsigned char   uint8_t;
typedef struct M4
{uint8_t M[4];
}M4;

随机生成GF（2）上4X4的矩阵

使用时间作种子 srand(time(NULL)) ，让rand() 产生的随机数。因为我们将4X4矩阵的每一行看作一个数，而一个数只有4个bit，所以将rand()%16，取值范围为0-15.

#include<stdlib.h>
#include<time.h>
void GetRandMatrix4(M4 *MT) {srand((unsigned int)time(NULL));for (int i = 0; i < 4; i++){(*MT).M[i]=rand()%16;}}

判断GF（2）上有限域矩阵是否可逆

跟上篇文章的求解思路是一样，只不过现在，4x4矩阵中所有元素为0和1，我们不需要考虑系数，并且我们把一行看成一个数，需要分别与0x08, 0x04, 0x02, 0x01进行逻辑与操作提取相应的比特位。
实现代码如下：

int is_invert(M4 *MT) {int flag;M4 temp;copyM4(MT, &temp);int row_index;//消除为下三角矩阵for (int k = 0; k < 4; k++) {if ((temp.M[k] & idM4[k]) != 0) {for (int i = k + 1; i < 4; i++){if ((temp.M[i] & idM4[k]) !=0) {temp.M[i] = temp.M[i] ^ temp.M[k];}}}else {flag = 1;for (int i = k + 1; i < 4; i++) {if ((temp.M[i] & idM4[k]) != 0) {swap4(i, k,&temp);flag = 0;break;}}if (flag) { printf("\n矩阵不可逆\n");return 0; }for (int i = k + 1; i < 4; i++){if ((temp.M[i] & idM4[k]) != 0) {temp.M[i] = temp.M[i] ^ temp.M[k];}}}}//判断对角线是否为0for (int i = 0; i < 4; i++) {if ((temp.M[i] & idM4[i]) == 0){printf("\n矩阵不可逆\n");return 0;}}return 1;
}

求GF（2）上有限域矩阵的可逆矩阵

在矩阵可逆的前提下，我们可以计算GF（2）有限域上的可逆矩阵，需要把矩阵扩展为 [ M ∣ E ] [M|E] [M∣E]，然后经过变化变为 [ E ∣ M − 1 ] [E|M^{-1}] [E∣M−1]， M − 1 M^{-1} M−1即为可逆矩阵，为了减少代码复杂度，这里我们不单独构造一个扩展矩阵 [ M ∣ E ] [M|E] [M∣E]，我们定义一个单位矩阵E，在每次M进行变化时，E跟着M进行变化，当M变为E时，E就变成了 M − 1 M^{-1} M−1.
求解步骤如下
1)将矩阵化简为下三角矩阵
2）将矩阵化为单位矩阵E
求解详细思路参考上篇文章，代码实现如下：

void getInvertMatrix(M4 *MT) {M4 M_invert;for (int i = 0; i < 4; i++){M_invert.M[i] = idM4[i];//初始化 E矩阵}for (int k = 0; k < 4; k++) {if (((*MT).M[k] & idM4[k]) != 0) {for (int i = k + 1; i < 4; i++){if (((*MT).M[i] & idM4[k]) != 0) {(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];}}}else {for (int i = k + 1; i < 4; i++) {if (((*MT).M[i] & idM4[k]) != 0) {swap4(i, k, MT);swap4(i, k, &M_invert);break;}}for (int i = k + 1; i < 4; i++){if (((*MT).M[i] & idM4[k]) != 0) {(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];}}}}//将右边的M矩阵，消除为单位矩阵Efor (int  k = 1; k < 4; k++){for (int i = 0; i < k; i++){for (int j = 0; j < 4; j++){if (((*MT).M[i]&idM4[k]) != 0){(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];}}}}printf("\n可逆矩阵为\n");printfM4(&M_invert);
}

最终实验结果如下,将每个数化为4位二进制数，即可得到4x4的可逆矩阵