使用 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++ 给出 addition/subtraction 的示例代码

Answer 1

Modular Arithmetic (addition/subtraction) using Crypto++

我们已经根据这个问题弥补了一些缺失的文档空白，所以我不会解决示例代码。改进后的文档可在 Integer Class Reference and Integer on the Crypto++ wiki.

获得

但是，使用 ModularArithmetic class 可能会出现错误或（至少）意外结果。 class 将自己描述为 "Ring of congruence classes modulo n"。从数学上讲，Ring 是一个具有闭包和两个定义明确的操作的群。

断开连接是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. Of particular interest is AbstractRing< T > Class Template Reference，ModularArithmetic 继承自它。它确认乘法和求幂是运算（并且它产生了助手，例如 Square）。

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

编辑 2

ModularArithmetic 似乎对 Add、Subtract 和朋友产生不正确结果的原因是 class 对于特定问题来说是快速的，它确实不使用欧几里德扩展算法执行完全归约。相反，它最多执行一次减法。这意味着要减去模数 p 的累加值 n 必须在 [0, 2p).

范围内

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

Modular Arithmetic addition and subtraction using Crypto++

c++

crypto++

modular-arithmetic