Modular Arithmetic addition and subtraction using Crypto++

I am very new to this, but I am trying to add two Integers in modular format using Crypto++ Library.

My program is very simple,

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);

But this simply didn't work. It complied fine, but it crashed when I was trying to run it.

Could anyone give a sample code for addition/subtraction using Crypto++ please

Solution

Modular Arithmetic (addition/subtraction) using Crypto++

We have closed some of the missing documentation gaps based on this question, so I won't address the sample code. The improved docs are available at Integer Class Reference and Integer on the Crypto++ wiki.

However, there may be a bug or (at least) unexpected results from using the ModularArithmetic class. The class describes itself as "Ring of congruence classes modulo n". Mathematically, a Ring is a group with closure and two well defined operations.

The disconnect is, which two operations are the ones included with ModularArithmetic<Integer>. Based on some sample code, it looks like its Multiply and Exponentiate, which is mostly expected (though it could have been Add and Multiply).

I don't think the mathematical definition of Ring gives ModularArithmetic a license to produce unexpected results. However, ModularArithmetic is kind of unique, and it may be accumulating intermediate results that one must then reduce using Multiply and Exponentiate. (It does accumulate results to speed up operations).

The open question for me is, what do we do... I'm trying to solicit some feedback at the moment on the issue.

Here's the test program:

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;
}

Here are the results:

$ ./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.

EDIT 1

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

So I had a chance to go though the source code and add more missing documentation. Of particular interest is AbstractRing< T > Class Template Reference, which ModularArithmetic inherits from. It confirms that multiply and exponentiation are the operations (and it gives rise to helpers, like Square).

What I am not clear about is why ModularArithmetic is providing Add, Subtract and friends but arriving at unexpected results. It could well be that its effectively accumulating the results and waiting to be reduced with a Multiply or Exponentiate, but I don't see any comments in the source code.

EDIT 2

The reason ModularArithmetic appears to produce incorrect results for Add, Subtract and friends is the class is meant to be fast for specific problems, and it does not perform a full reduction using the Euclidean extended algorithm. Rather, it performs at most one subtraction. That means the accumulated value n to be reduced by the modulus p must be in the range [0, 2p).