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

问题描述

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

I have a long integer number, but it is stored not in decimal form, but as set of remainders.

所以，我没有N号，但有一组这样的余数:

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

我知道，N小于这些质数的乘积，因此，中国余数定理确实在这里起作用( http ://en.wikipedia.org/wiki/Chinese_remainder_theorem ).

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 ).

如果我有6个余数，如何用小数点恢复N?妙用的是任何程序都可以做到这一点(C/C + GMP/C ++/perl/java/bc ).

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).

例如，最小N可以拥有这组余数:

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)

推荐答案

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

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)

用gcc -std=c99 -lgmp编译.另外，请根据您的情况更改大小.

Compile with gcc -std=c99 -lgmp. Also change size for your case.

#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

N is 703066055325632897509116263399480311

这篇关于从数个余数中还原一个数字(中文余数定理)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！