c++ - 无法理解/使用修改后的 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-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、使得 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'，并返回 1 当且仅当 g 已经改变。

正常使用下，输入值g满足-a/2 < g <= a/2；然而，这在早期版本中没有记录或强制执行，所以为了保持向后兼容性，没有任何限制在 g.但是，如果 -a/2 < g <= a/2，此例程运行得更快，例程做的第一件事就是使这个条件坚持。

另外，在正常使用下，a和p都是奇数；然而，常规即使不是这样，仍然会起作用。

例程基于以下简单事实。

令-a/2 < g <= a/2，令h满足 * g + a h = G (mod p); * -p/2 < h <= p/2。此外，如果 p = 2*h 且 g > 0，则设置 g' := g - a h;否则，设置 g' := g + a h。那么这样定义的g'满足上述要求。很容易看出 g 满足同余条件。唯一的事情是检查“平衡”条件 -a'/2 < g' <= a'/2 也成立。

Answer 1

NTL::CRT 实现所谓的“增量中文剩余”这是迭代求解同时同余系统的数值方法。因此，增量中国余数与中国余数定理具有相同的目标(和结果)，但前者在一次迭代中解决了两个同时同余的系统。在第二次迭代中，它解决了第一次迭代和第三次同余的输出系统，依此类推。与您找到三个数字的 GCD = GCD(GCD(n1, n2), n3) 的方法相同。让我们用下面的例子(同余系统)来证明NTL::CRT和中国经典剩余定理的计算给出相同的结果。我们应该找到 a' 使得 a' = 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;
}

输出:

1st iteration a: -7 p: 20

2nd iteration a: -47 p: 140

所以结果是 a' == 93 (-47 + 140 == 93)。与中国古典余数算法相同。