反转 NTL 中的ZZ_p矩阵

Question

我正在尝试生成一个随机二进制矩阵及其逆模 q，其中 q 是 2 的幂。有时，当我的矩阵的行列式是可逆模 q 时(因此Z_q上的矩阵是可逆的(，我会收到错误"InvMod：逆未定义中止(核心转储("，其他时候计算逆。我做错了什么？

#include <iostream>
//NTL files
#include <NTL/ZZ_p.h>
#include <NTL/vec_vec_ZZ_p.h>
#include <NTL/LLL.h>
#include <NTL/matrix.h>
#include <NTL/vector.h>
#include <NTL/tools.h>
#include <NTL/ZZ.h>
#include <NTL/vec_vec_ZZ.h>
using namespace std;
using namespace NTL;
int main(){//task generate a random matrix S with 0/1 entries stored as a ZZ_p matrix, then generate a random, invertible S 
int nn = 8;
ZZ n = ZZ(nn);
ZZ N = ZZ(0);
ZZ q; power2(q, 4);
ZZ_p::init(q);
mat_ZZ S; S.SetDims(nn,nn); 
for(int i = 0; i<nn; i++){
    for(int j = 0; j<nn; j++){
        S[i][j] = RandomBits_ZZ(1);     
    }
}
mat_ZZ_p S1; S1.SetDims(nn,nn);//copy to ZZ_P
mat_ZZ_p R; R.SetDims(nn,nn);//will set to inverse if 
cout<<"The random matrix is S = "<<endl; //print S
for(int i = 0; i<nn; i++){
    for(int j=0; j<n;j++){
        cout<<S[i][j]<<", ";
    } cout<<endl;
}
ZZ d; determinant(d,S); ZZ_p d1; conv(d1, d % q);
if(GCD(q,d) == 1){//convert to mod q datatype
    for(int i = 0; i<nn; i++){
        for(int j = 0; j<nn; j++){
            conv(S1[i][j], S[i][j]);        
        }
    }
    //let's invert the matrix and print it!
    cout<<"The random matrix is R = "<<endl; //print R
    R = inv(S1); //mul(R,R,S1);
    for(int i = 0; i<nn; i++){
        for(int j=0; j<n;j++){
            cout<<R[i][j]<<", ";
        } cout<<endl;
    }
}
cout<<endl<<"det of S is "<<d<<" and this mod q is "<<d1<<endl;
cout<<"Our modulus is "<< q <<endl;
return 0;
}

Answer 1

如果行列式是可逆模q这只意味着存在一个逆矩阵。但是计算这个矩阵的算法仍然可以达到一个点，它需要计算一个没有矩阵的元素的逆

。

如果q是素数，则没有这个问题。

顺便说一下，这是您的代码的简化版本。

#include <iostream>
//NTL files
#include <NTL/mat_ZZ_p.h>
using namespace std;
using namespace NTL;
int main()
{//task generate a random matrix S with 0/1 entries stored as a ZZ_p matrix, then generate a random, invertible S
    int nn = 8;
    ZZ q;
    power2(q, 4);
    ZZ_p::init(q);
    mat_ZZ_p S;
    S.SetDims(nn, nn);
    for(int i = 0; i < nn; i++)
    {
        for(int j = 0; j < nn; j++)
        {
            S[i][j] = conv<ZZ_p>(RandomBits_ZZ(1));
        }
    }
    mat_ZZ_p R;
    R.SetDims(nn, nn);//will set to inverse if
    cout << "The random matrix is S = " << endl << S;
    ZZ_p d;
    determinant(d, S);
    cout << endl << "det(S) = " << d << endl;
    cout << "q = " << q << endl;
    if(GCD(conv<ZZ>(d), q) == 1)
    {
        // let's invert the matrix and print it!
        R = inv(S);
        cout << "The random matrix is R = " << R << endl;
    }
    return 0;
}