math - 从数个余数中还原一个数字(中文余数定理)

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

因此，我没有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/bc)。

例如，最小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)

最佳答案

您链接的文章已经提供了a constructive algorithm to find the solution。

基本上，对于每个i，您都可以求解整数方程ri*ni + si*(N/ni) = 1，其中N = n1*n2*n3*...。 ri和si在这里是未知的。这可以通过extended euclidean algorithm解决。它非常流行，您可以轻松找到任何语言的示例实现。

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

关于math - 从数个余数中还原一个数字(中文余数定理)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5286898/