Restaurer un nombre à partir de plusieurs de ses restes (théorème du reste chinois)

Question

J'ai un nombre entier long, mais il est stocké non sous forme décimale, mais comme ensemble de restes.

Donc, je n'ai pas le nombre N, mais un ensemble de ces Restes:

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

Je sais que N est inférieur à la multiplication de ces nombres premiers, alors théorème chinois ne fonctionne ici (http://en.wikipedia.org/wiki/Chinese_remainder_theorem).

Comment puis-je restaurer N en décimal, si j'ai ce 6 reste? Le merveilleux sera n'importe quel programme pour ce faire (C/C + GMP/C++/perl/java/bc).

Par exemple, ce que N minimal peut avoir cet ensemble de Restes:

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

Voici le code (C + GMP), en fonction de ce code LGPL par Ben Lynn blynn@github; stanford de l'algorithme Garner (trouvé avec RIP Google Recherche de code par requête garner mpz_t): https://github.com/blynn/pbc/blob/master/guru/indexcalculus.c (Une partie de son Le PBC (Pairing- Bibliothèque cryptographique basée)

Compile avec gcc -std=c99 -lgmp. Changez également la taille pour votre cas.

#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); 
} 

Exemple est résolu:

$ ./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 est 703066055325632897509116263399480311

Answer 2

L'article que vous liez fournit déjà a constructive algorithm to find the solution.

Fondamentalement, pour chaque i vous résolvez l'équation entière ri*ni + si*(N/ni) = 1 où N = n1*n2*n3*.... Les ri et si sont inconnus ici. Cela peut être résolu par extended euclidean algorithm. C'est très populaire et vous n'aurez aucun problème à trouver des exemples d'implémentations dans n'importe quelle langue. Puis, en supposant ei = si*(N/ni), la réponse est sum(ei*ai) pour chaque i.
Tout cela est décrit dans cet article, avec preuve et exemple.