c++ - 使用Crypto++的模块化算术加法和减法

我对此很陌生，但是我正在尝试使用Crypto ++ Library以模块化格式添加两个Integer。

我的程序很简单，

AutoSeededRandomPool prng;
Integer r0, m;

m = Integer( prng, 64);
r0 = Integer( prng, 64);

cout << "m: " << std::hex << m << endl;
cout << "r0:" << std::hex << r0 << endl;

Integer n1(r0 + m);

但这根本行不通。它符合要求，但是在我尝试运行它时崩溃了。

任何人都可以使用Crypto ++给出用于加/减的示例代码。

最佳答案

基于此问题，我们已经弥补了一些缺少的文档空白，因此我将不介绍示例代码。可以从Integer Class Reference和Integer on the Crypto++ wiki获得改进的文档。

但是，使用ModularArithmetic class可能会导致错误或(至少)意外的结果。该类将自己描述为“模n的同余类的环”。从数学上讲，环是一个具有闭包和两个定义明确的操作的组。

断开连接是ModularArithmetic<Integer>包含的两个操作。根据一些示例代码，它看起来像Multiply和Exponentiate，这是大多数人所期望的(尽管它本来可以是Add和Multiply)。

我不认为Ring的数学定义可以使ModularArithmetic获得产生意外结果的许可。但是，ModularArithmetic是唯一的，它可能会累积中间结果，然后必须使用Multiply和Exponentiate减少这些中间结果。 (它会累积结果以加快操作速度)。

对我来说，开放的问题是，我们该怎么办...目前，我正试图就此问题征求一些反馈。

这是测试程序:

int main(int argc, char* argv[])
{
  Integer m("4294967295"), n("0x1000000000000000000000000000000"), j;
  j = 1999;

  ModularArithmetic ma(j);

  cout << "n+m mod j: " << ma.Add(n, m) << endl;
  cout << "  cross-check: " << (n+m) % j << endl;
  cout << "n-m mod j: " << ma.Subtract(n, m) << endl;
  cout << "  cross-check: " << (n-m) % j << endl;
  cout << "n*m mod j: " << ma.Multiply(n, m) << endl;
  cout << "  cross-check: " << (n*m) % j << endl;
  cout << "n/m mod j: " << ma.Divide(n, m) << endl;
  cout << "  cross-check: " << (n/m) % j << endl;
  cout << "n%m mod j: " << ma.Reduce(n, m) << endl;
  cout << "  cross-check: " << (n%m) % j << endl;
  cout << "n^m mod j: " << ma.Exponentiate(n, m) << endl;
  cout << "  cross-check: " << a_exp_b_mod_c(n,m,j) << endl;

  return 0;
}

结果如下:

$ ./test.exe
n+m mod j: 1329227995784915872903807064575309872.
  cross-check: 1755.
n-m mod j: 1329227995784915872903807055985377281.
  cross-check: 50.
n*m mod j: 266.
  cross-check: 266.
n/m mod j: 599.
  cross-check: 1997.
n%m mod j: 1329227995784915872903807055985377281.
  cross-check: 1608.
n^m mod j: 1326.
  cross-check: 1326.

编辑1



因此，我有机会介绍了源代码和add more missing documentation。特别值得关注的是 AbstractRing< T > Class Template Reference，它是ModularArithmetic继承的。它确认乘法和幂运算是运算符(并产生了辅助函数，如Square)。

我不清楚的是，为什么ModularArithmetic提供Add，Subtract和 friend ，但是却获得了意外的结果。很有可能是它有效地累积了结果并等待被Multiply或Exponentiate减少，但是我在源代码中看不到任何注释。

编辑2
ModularArithmetic似乎会为Add，Subtract和friends产生不正确结果的原因是该类旨在快速解决特定问题，并且无法使用Euclidean扩展算法进行完全还原。相反，它最多执行一次减法。这意味着要减少模数n的累加值p必须在[0, 2p)范围内。