c++ - 使用Eigen C++库反转矩阵mod-26

我正在尝试编写一个程序来破解C ++中任意尺寸（MxM）的希尔密码。该过程的一部分要求我计算矩阵的mod-26逆。

例如，2x2数组的模逆

14 3
11 0

是

0 19
9 24

我有一个函数只能对2x2数组完成此操作，这还不够。我知道很难在大维数组上计算逆，因此我使用的是Eigen C ++库。但是，Eigen inverse（）函数为我提供了上述矩阵的逆函数：

0.000 0.091
 0.333 -0.424

如何使用Eigen计算任何尺寸的矩阵所需的模数26逆数？

最佳答案

尝试这个：

#include <iostream>
#include <functional>
#include <Eigen/Dense>

using namespace Eigen;
using namespace std;

int inverse_mod_26(int d)
{
   // We're not going to use Euclidean Alg. or
   // even Fermat's Little Theorem, but brute force
   int base = 26, inv = 1;

   while ( (inv < base) &&
       (((d * ++inv) % 26) != 1)) {}

   return inv;
}

int main(int argc, char **argv)
{

   Matrix2d m, minv;
   int inv_factor;
   m << 14, 3, 15, 0;
   double mdet = m.determinant();

   minv = mdet * m.inverse();
   transform(&minv.data()[0], &minv.data()[4], &minv.data()[0],
         [](double d){ return static_cast<int>(d) % 26;});
   if ((static_cast<int>(mdet) % 26) == 1) { // no further modification}
   else
     {
        inv_factor = inverse_mod_26(std::abs((m * minv)(0,0)));
        if (inv_factor == 26)
          {
             cerr << "No inverse exists!" << endl;
             return EXIT_FAILURE;
          }

        transform(&minv.data()[0], &minv.data()[4], &minv.data()[0],
              [=](double d){ return static_cast<int>(d) * inv_factor;});
     }

   cout << "m = " << endl << m << endl;
   cout << "minv = " << endl << minv << endl;
   cout << "(m * minv) = " << endl << m * minv << endl;

   return 0;
}

对于底座26，这是2x2的情况，但可以轻松修改。该算法依赖于修改法线矩阵逆，并且，如果您愿意，可以很容易地解释。如果您的原始矩阵的行列式（通常意义上）不是26的素数；即，如果GCD(det(m), 26) != 1，则它不会取反。

提示：为避免此问题，请使用上面的else子句，将三个任意字符填充到字典中，使大小为29（即质数），并会满足上面的GCD属性。

关于c++ - 使用Eigen C++库反转矩阵mod-26，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20374125/