Why did it show "InvMod: inverse undefined" when used CRT algorithm in NTL library?

Question

I tried to use NTL library to implement my cryptographic algorithm. However, it showed me someting wromg about CRT algorithm. CRT is short for Incremental Chinese Remaindering and it is defined as following:

long CRT(ZZ& a, ZZ& p, const ZZ& A, const ZZ& P);
long CRT(ZZ& a, ZZ& p, long A, long P);

// 0 <= A < P, (p, P) = 1; computes a' such that a' = a mod p, 
// a' = A mod P, and -p*P/2 < a' <= p*P/2; sets a := a', p := p*P, and
// returns 1 if a's value has changed, otherwise 0

I try to print some information:

gp=66390828312651972973888361332364813613478546962956830307987136462065800330260786554389230936903970584093871405496526397214600259238471440684133633914352198492704004953513651583287557225250450851122687829965259605518687677556714602317993643325112503010372335796589795208660430772233273662752270218833954206912
p=98506238639786519141405322641812326504550334169475033833322673238957789026078361022953456930946799879629297087483487500221235712451981623924607546413344684294639373306430972887026133598448706655301440705253664704851471711197893571186626487501140015523931128287493592419972025673134065648304689552713586835457
gq=6667000274529267578982370009668139148348778725432024700386402060811738943238338877475151419711063751789939702415071471603295111504118310469114424237809527
q=11378762793182988817702088080680425474862067132459357853502156713056912474438574734825983540828752440930678737903819042152986539729875178831578851503505409
InvMod: inverse undefined

I called CRT as below:

// ...
std::cout << "gp=" << gp << std::endl;
std::cout << "p=" << p << std::endl;
std::cout << "gq=" << gq << std::endl;
std::cout << "q=" << q << std::endl;
NTL::CRT(gp, p, gq, q);

Answer 1

From ntl/ZZ.cpp:1307, the following comments are given for the CRT function:

// Chinese Remaindering.
[...]
// This function takes as input g, a, G, p,
// such that a > 0, 0 <= G < p, and gcd(a, p) = 1.
[...]
long CRT(ZZ& gg, ZZ& a, long G, long p)

In your case, we need gcd(p, q) = 1, but with your values, gcd(p, q) = q, i.e. p = r * q, where

r = 8657025410425249234452045797441790045805303296607662\
201360892817104202207969817487169683905119008751440550350704\
462002980862924347497458107362187486953473

The result was obtained using Big Number Calculator online.

In other words, p and q must be relatively prime - but they are not.

The test for relative primality is performed within InvMod:

long InvMod(long a, long n)
{
   long d, s, t;

   XGCD(d, s, t, a, n);
   if (d != 1) {
      InvModError("InvMod: inverse undefined");
   }
   if (s < 0)
      return s + n;
   else
      return s;
}

And InvMod is invoked from CRT as follows:

long CRT(ZZ& gg, ZZ& a, long G, long p)
{
   if (p >= NTL_SP_BOUND) {
      ZZ GG, pp;
      conv(GG, G);
      conv(pp, p);
      return CRT(gg, a, GG, pp);
   }

   [...]

   long a_inv;
   a_inv = rem(a, p);
   a_inv = InvMod(a_inv, p);

   [...]
}

Since p and q are not relatively prime, rem(p, q) = 0, and the InvMod(0, q) invocation fails.