无法理解/使用修改后的CRT功能

Question

我正在从事密码学项目。我们需要使用NTL big num库，尤其是使用该库的CRT函数生成公共密钥。该库的CRT功能未使用标准的中国剩余定理算法；它是修改后的版本，我无法确切了解其工作方式。

CRT（a，b，c，d）

据我所知，如果a％b == c％d，CRT会返回1，但情况并非总是如此，在以下结果中，我将b = 5设置为d = 6，而a = c是介于1和2之间的随机整数-6：

a％b：3 c％d：3 CRT：1

a％b：0 c％d：5 CRT：1

a％b：2 c％d：2 CRT：0

a％b：1 c％d：1 CRT：0

a％b：4 c％d：4 CRT：1

a％b：1 c％d：0 CRT：1

以下是库中CRT功能的代码。ZZ是一种库特定类型，用于表示大数。

long CRT(ZZ& gg, ZZ& a, const ZZ& G, const ZZ& p){
  long modified = 0;

  ZZ g;

  if (!CRTInRange(gg, a)) {
    modified = 1;
    ZZ a1;
    rem(g, gg, a);    // g = gg%a
    RightShift(a1, a, 1);    // a1 = (a >> 1) 
    if (g > a1) sub(g, g, a);
  }
  else
  g = gg;


  ZZ p1;
  RightShift(p1, p, 1);

  ZZ a_inv;
  rem(a_inv, a, p);
  InvMod(a_inv, a_inv, p);    // a_inv = a_inv^{-1} mod p, 0 <= a_inv < p  

  ZZ h;
  rem(h, g, p);
  SubMod(h, G, h, p);    // return h = (G-h)%p
  MulMod(h, h, a_inv, p);    // return h = (h*a_inv)%p
  if (h > p1)
  sub(h, h, p);

  if (h != 0) {
    modified = 1;
    ZZ ah;
    mul(ah, a, h);

  if (!IsOdd(p) && g > 0 &&  (h == p1))
     sub(g, g, ah);
  else
     add(g, g, ah);
  }

  mul(a, a, p);
  gg = g;

  return modified;
  }

以下是图书馆提供的唯一信息。我不太擅长离散数学。谁能用外行的术语确切地解释此功能的作用？

剩下的中文。

此版本是v3.7的新增功能，并且比以前的版本明显更简单，更快。

该函数将g，a，G，p作为输入g，使得a> 0、0 <= G <p和gcd（a，p）=1。它计算a'= a * p和g'使得* g'= g（mod a）; * g'= G（mod p）; * -a'/ 2 <g'<= a'/ 2。然后，它设置g：= g'和a：= a'，并且如果g已更改，则返回1。

在正常使用下，输入值g满足-a / 2 <g <= a / 2; 但是，在早期版本中没有记录或强制执行此操作，因此为了保持向后兼容性，对g没有限制。但是，如果-a / 2 <g <= a / 2，则该例程运行得更快，并且该例程要做的第一件事是使该条件成立。

同样，在正常使用下，a和p均为奇数；但是，即使不是这样，例程仍然可以工作。

该例程基于以下简单事实。

令-a / 2 <g <= a / 2，令h满足* g + ah = G（mod p）; * -p / 2 <h <= p / 2。此外，如果p ＝ 2 * h并且g＞ 0，则设置g′：＝ g-ah；否则，设置g'：= g + a h。这样定义的g'满足上述要求。显而易见，g满足全等条件。唯一的事情是检查“平衡”条件-a'/ 2 <g'<= a'/ 2是否成立。

Answer 1

NTL :: CRT实现所谓的“增量中文余数”。 这是一种迭代求解同时满足系统的数值方法。因此，增量式中文余数与中文余数定理具有相同的目标（AND RESULT），但前者一次迭代地解决了两个同时全等的系统。在第二次迭代中，它解决了第一次迭代和第三次一致性的输出系统，等等。用相同的方法可以找到三个数字的GCD = GCD（GCD（n1，n2），n3）。让我们用以下示例（同余系统）证明NTL :: CRT和经典中国余数定理的计算得出相同的结果。我们应该找到一个'a'= a1 = b1 mod m1，a'= b2 mod m2和a'= b3 mod m3。

a'== 93

现在让我们用NTL库解决同一系统。有两个CRT通话。

#include <cassert>
#include "NTL/ZZ.h"

int main()
{
    using std::cout;
    using std::endl;
    using namespace NTL;
    ZZ b1, b2, b3;
    ZZ m1, m2, m3;
    b1 = 1;
    b2 = 3;
    b3 = 2;

    m1 = 4;
    m2 = 5;
    m3 = 7;

    ZZ a, p, A, P; // named as in CRT implementation

    // first iteration
    a = b1; p = m1;
    A = b2; P = m2;
    assert(CRT(a, p, A, P)); // CRT returns 1 if a's value changed

    cout << "1st iteration a: " << a << "\tp: " << p << endl;

    // next iteration   
    // a and p == m1 * m2 contain result from first iteration
    A = b3; P = m3;
    assert(CRT(a, p, A, P));

    cout << "2nd iteration a: " << a << "\tp: " << p << endl;
    return 0;
}

输出：

第一次迭代a：-7 p：20

第2次迭代a：-47 p：140

因此结果是a'== 93（-47 + 140 == 93）。与经典中文余数算法相同。