从几个余数中恢复一个数（中国余数定理）

Question

我有一个长整数，但它不是以十进制形式存储，而是作为余数集存储。

所以，我没有 N 数字，而是一组这样的余数：

r_1 = N % 2147483743
r_2 = N % 2147483713
r_3 = N % 2147483693
r_4 = N % 2147483659
r_5 = N % 2147483647
r_6 = N % 2147483629

我知道，N 小于这些素数的乘积，所以中国余数定理在这里确实有效（ http://en.wikipedia.org/wiki/Chinese_remainder_theorem ）。

如果我有这 6 个余数，我怎样才能以十进制恢复 N？ 任何程序都可以做到这一点（C/C+GMP/C++/perl/java /公元前）。

例如，最小 N 可以得到这组余数：

r_1 = 1246736738 (% 2147483743)
r_2 = 748761 (% 2147483713)
r_3 = 1829651881 (% 2147483693)
r_4 = 2008266397 (% 2147483659)
r_5 = 748030137 (% 2147483647)
r_6 = 1460049539 (% 2147483629)

Answer 1

您链接的文章已经提供了寻找解决方案的建设性算法。

基本上，对于每个i，您求解整数方程ri*ni + si*(N/ni) = 1，其中N = n1*n2*n3*.. .。 ri 和 si 在这里是未知的。这可以通过扩展欧几里德算法来解决。它非常流行，您可以毫无问题地找到任何语言的示例实现。

然后，假设ei = si*(N/ni)，则每个i的答案是sum(ei*ai)。
所有这些都在那篇文章中进行了描述，并附有证据和示例。

Answer 2

这里是代码 (C+GMP)，基于 Ben Lynn blynn@github 的 LGPL 代码； stanford 的 Garner 算法（通过 RIP Google Code Search 通过查询 garner mpz_t 找到）：
https://github.com/blynn/pbc/blob/master/guru /indexcalculus.c
（他的 PBC（基于配对的加密）库的一部分）

使用 gcc -std=c99 -lgmp 进行编译。还要根据您的情况更改尺寸。

#include <gmp.h>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

// Garner's Algorithm.
// See Algorithm 14.71, Handbook of Cryptography.

//    x - result    v residuals    m - primes   t-size of vectors
static void CRT(mpz_t x, mpz_ptr *v, mpz_ptr *m, int t) {
  mpz_t u;
  mpz_t C[t];
  int i, j;

  mpz_init(u);
  for (i=1; i<t; i++) {
    mpz_init(C[i]);
    mpz_set_ui(C[i], 1);
    for (j=0; j<i; j++) {
      mpz_invert(u, m[j], m[i]);
      mpz_mul(C[i], C[i], u);
      mpz_mod(C[i], C[i], m[i]);
    }
  }
  mpz_set(u, v[0]);
  mpz_set(x, u);
  for (i=1; i<t; i++) {
    mpz_sub(u, v[i], x);
    mpz_mul(u, u, C[i]);
    mpz_mod(u, u, m[i]);
    for (j=0; j<i; j++) {
      mpz_mul(u, u, m[j]);
    }
    mpz_add(x, x, u);
  }

  for (i=1; i<t; i++) mpz_clear(C[i]);
  mpz_clear(u);
}

const int size=6; // Change this please

int main()
{
    mpz_t res;
    mpz_ptr t[size], p[size];
    for(int i=0;i<size;i++) { 
        t[i]=(mpz_ptr)malloc(sizeof(mpz_t));
        p[i]=(mpz_ptr)malloc(sizeof(mpz_t));
        mpz_init(p[i]);
        mpz_init(t[i]);
    }
    mpz_init(res);

    for(int i=0;i<size;i++){
        unsigned long rr,pp;
        scanf("%*c%*c%*c = %lu (%% %lu)\n",&rr,&pp);
        printf("Got %lu res on mod %% %lu \n",rr,pp);
        mpz_set_ui(p[i],pp);
        mpz_set_ui(t[i],rr);
    }

    CRT(res,t,p,size);

    gmp_printf("N = %Zd\n", res);
}

示例已解决：

$ ./a.out
r_1 = 1246736738 (% 2147483743)
r_2 = 748761 (% 2147483713)
r_3 = 1829651881 (% 2147483693)
r_4 = 2008266397 (% 2147483659)
r_5 = 748030137 (% 2147483647)
r_6 = 1460049539 (% 2147483629)

Got 1246736738 res on mod % 2147483743 
Got 748761 res on mod % 2147483713 
Got 1829651881 res on mod % 2147483693 
Got 2008266397 res on mod % 2147483659 
Got 748030137 res on mod % 2147483647 
Got 1460049539 res on mod % 2147483629 
N = 703066055325632897509116263399480311

N 为 703066055325632897509116263399480311

Answer 3

以下是基于此 Rosetta Code 任务的 Python 3 实现：https://rosettacode.org/wiki/Chinese_remainder_theorem

from functools import reduce
from operator import mul    

def chinese_remainder(n, a):
    """
    Chinese Remainder Theorem.

    :param n: list of pairwise relatively prime integers
    :param a: remainders when x is divided by n
    """
    s = 0
    prod = reduce(mul, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        s += a_i * inverse(p, n_i) * p
    return s % prod    

def inverse(a, b):
    """
    Modular multiplicative inverse.
    """
    b0 = b
    x0, x1 = 0, 1
    if b == 1:
        return 1
    while a > 1:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += b0
    return x1    

n = [2147483743, 2147483713, 2147483693, 2147483659, 2147483647, 2147483629]
a = [1246736738, 748761, 1829651881, 2008266397, 748030137, 1460049539]

print(chinese_remainder(n, a))  # 703066055325632897509116263399480311

Python 的一个很好的特性是它天然支持任意大的整数。

Answer 4

只需添加此处的一点理论及其逐字实现python：

from math import prod
    
def CRT_residue(a, m):
    # assert len(a) == len(m)
    n, P = len(a), prod(m)
    M = [P // m[i] for i in range(n)]  # M_i s
    # modular inverse of M_i to be computed with Extended Euclid algorithm
    # extract the Bézout coefficient corresponding to M_i
    N = [gcd_ext(M[i], m[i])[1] for i in range(n)] # N_i s
    return sum([a[i]*M[i]*N[i] for i in range(n)]) % P

def gcd_ext(a, b): # Extended Euclid algorithm
    x0, y0 = 1, 0
    x1, y1 = 0, 1
    while b:
        q = a // b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
        a, b = b, a % b
    return a, x0, y0 # return GCD and the Bézout coefficients

# given example
m = [2147483743, 2147483713, 2147483693, 2147483659, 2147483647, 2147483629]
a = [1246736738, 748761, 1829651881, 2008266397, 748030137, 1460049539]
print(CRT_residue(a, m))
# 703066055325632897509116263399480311

另一种可能性是使用 加纳算法。