理解/使用改進的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）。與經典中文餘數算法相同。