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

Question

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

我的程序很简单，

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++ 进行加法/减法的示例代码

Answer 1

Modular Arithmetic (addition/subtraction) using 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

The disconnect is, which two operations are the ones included with ModularArithmetic<Integer>...

所以我有机会查看源代码和 add more missing documentation .特别感兴趣的是 AbstractRing< T > Class Template Reference ，这ModularArithmetic继承自。它确认乘法和求幂是运算(并且它产生了助手，如 Square )。

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

---

编辑 2

原因ModularArithmetic似乎为 Add 产生了不正确的结果, Subtract和 friend 们是这个类是为了快速解决特定问题，它不会使用欧几里德扩展算法执行完全减少。相反，它执行至多 一次减法。即累计值n减去模数 p必须在 [0, 2p) 范围内.