前言
上篇文章介绍了实数域上的线性代数求解可逆矩阵的方法,但有时候我们有更复杂的需求,如在有限域上求解可逆矩阵,有限域是一个很有意思的东西,它的知识可见这篇文章
今天我们简单描述如何在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];
}
}
}
}
//判断对角线是否为0
for (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
求解详细思路参考上篇文章,代码实现如下:文章来源:https://www.toymoban.com/news/detail-481606.html
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矩阵,消除为单位矩阵E
for (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的可逆矩阵
文章来源地址https://www.toymoban.com/news/detail-481606.html
到了这里,关于密码学基础——GF(2)有限域上的矩阵求逆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!