I have a long integer number, but it is stored not in decimal form, but as set of remainders.
So, I have not the N
number, but set of such remainders:
r_1 = N % 2147483743
r_2 = N % 2147483713
r_3 = N % 2147483693
r_4 = N % 2147483659
r_5 = N % 2147483647
r_6 = N % 2147483629
I know, that N is less than multiplication of these primes, so chinese remainder theorem does work here ( http://en.wikipedia.org/wiki/Chinese_remainder_theorem ).
How can I restore N
in decimal, if I have this 6 remainders? The wonderful will be any program to do this (C/C+GMP/C++/perl/java/bc).
For example, what minimal N can have this set of remainders:
r_1 = 1246736738 (% 2147483743)
r_2 = 748761 (% 2147483713)
r_3 = 1829651881 (% 2147483693)
r_4 = 2008266397 (% 2147483659)
r_5 = 748030137 (% 2147483647)
r_6 = 1460049539 (% 2147483629)
Here the code (C+GMP), based on this LGPL code by Ben Lynn blynn@github; stanford of Garner algorithm (found with RIP Google Code Search by query garner mpz_t): https://github.com/blynn/pbc/blob/master/guru/indexcalculus.c (Part of his The PBC (Pairing-Based Crypto) library)
Compile with
gcc -std=c99 -lgmp
. Also change size for your case.Example is solved:
N is 703066055325632897509116263399480311