理解/使用改进的CRT功能时遇到的问题

Question

我正在开发一个加密项目。我们需要使用NTL的大数字库，特别是使用库的CRT函数来生成公钥。该库的CRT函数不使用标准的中国剩余定理算法;它是一个修改版本，我无法准确理解它是如何工作的。

CRT（A，B，C，d）

从我可以告诉CRT如果A％B == C％d返回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 CR T：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， 使得> 0，0 < = G < p和GCD（A，P）= 1 它计算一个” = 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 < = 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实现所谓的“Incremental Chinese Remainsdering” 这是迭代求解同时同余系统的数值方法。 所以增量式中文有同一个目标（与结果）作为中国剩余定理但前者在一次迭代中解决了两个同时同余的系统。在第二次迭代中，它解决了第一次迭代和第三次同余的输出系统等问题。用同样的方法找到三个数字的GCD = GCD（GCD（n1，n2），n3）。 让我们证明NTL :: CRT和经典中国剩余定理的计算给出与以下示例（同余系统）相同的结果。我们应该找到'a'= b1 mod m1，a'= b2 mod m2和a'= b3 mod m3。

一个” == 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; 
} 

输出：

第一迭代中：-7号码：20

第二迭代中：-47号码：140

所以结果是” == （-47 + 140 == 93）。与经典中文余数算法相同。