reconstruct.hpp

Go to the documentation of this file.

void chinese(mpz_t res,
         const mpz_t r1, const mpz_t m1,
         const mpz_t r2, const mpz_t m2)
{
  mpz_t tmpres;
  int swap=1;
  mpz_t bez1_1,bez1_2;
  mpz_t bez2_1,bez2_2;
  mpz_t a,b;
  mpz_t q;
  mpz_init(tmpres);
  mpz_init(q);
  mpz_init_set(a,m1);
  mpz_init_set(b,m2);
  mpz_init_set_si(bez1_1,1);
  mpz_init_set_si(bez1_2,0);
  mpz_init_set_si(bez2_1,0);
  mpz_init_set_si(bez2_2,1);
  
  if (mpz_cmp(a,b)<0)
    {
    mpz_swap(a,b);
    mpz_swap(bez1_1,bez2_1);
    mpz_swap(bez1_2,bez2_2);
    swap*=-1;
      }
  for(;mpz_cmp_si(b,1);)
  {
    
    mpz_tdiv_qr(q,a,a,b);
    mpz_submul(bez1_1,bez2_1,q);
    mpz_submul(bez1_2,bez2_2,q);
    swap*=-1;
    mpz_swap(a,b);
    mpz_swap(bez1_1,bez2_1);
    mpz_swap(bez1_2,bez2_2);
  }
  mpz_mul(tmpres,bez2_2,m2);
  mpz_mul(tmpres,tmpres,r1);
  mpz_mul(q,bez2_1,m1);
  mpz_mul(q,q,r2);
  mpz_add(tmpres,tmpres,q);
  mpz_mul(q,m1,m2);
  mpz_mod(tmpres,tmpres,q);
  
  mpz_set(res,tmpres);
  mpz_clear(tmpres);
  mpz_clear(q);
  mpz_clear(bez1_1);
  mpz_clear(bez1_2);
  mpz_clear(bez2_1);
  mpz_clear(bez2_2);
  mpz_clear(a);
  mpz_clear(b);
  
}
         
int reconstruct(mpq_t res, const mpz_t u, const mpz_t m)
{
  int ret=-1;
  mpz_t N;
  mpz_t r0,t0;
  mpz_t r1,t1;
  mpz_t q,tmp;
  mpz_init_set(N,m);
  mpz_fdiv_q_ui(N,N,2);
  mpz_sqrt(N,N);
  mpz_init_set(r0,m);
  mpz_init_set(r1,u);
  mpz_mod(r1,u,m);
  mpz_init(t0);
  mpz_init_set_ui(t1,1);
  mpz_init(q);
  mpz_init(tmp);
  //printf(" N ");  mpz_out_str(stdout,10,N);printf("\n");
  while(mpz_cmp(r1,N)>0)
    {
      //  printf("passage\n");
      mpz_fdiv_q(q,r0,r1);
      mpz_set(tmp,r1);
      //r1=r0-q*r1;
      mpz_mul(r1,r1,q);
      mpz_neg(r1,r1);
      mpz_add(r1,r0,r1);
      //
      mpz_set(r0,tmp);
      //
      //t1=t0-q*t1;
      mpz_set(tmp,t1);
      mpz_set(t1,t0);
      mpz_submul(t1,q,tmp);
      //
      //t0=tmp;
      mpz_set(t0,tmp);
      //printf("t0 ");mpz_out_str(stdout,10,t0);printf("\n");  
      //printf("r0 ");mpz_out_str(stdout,10,r0);printf("\n");
      //printf("t1 ");mpz_out_str(stdout,10,t1);printf("\n");
      //printf("r1 ");mpz_out_str(stdout,10,r1);printf("\n");
    }
  if(mpz_cmp_si(t1,0)<0)
    {
      //t1=-1*t1;
      mpz_neg(t1,t1);
      //r1=-1*r1;
      mpz_neg(r1,r1);
    }
  mpz_gcd(tmp,r1,t1);
  if((mpz_cmp(t1,N)<0) && (mpz_cmp_si(tmp,1)==0))
    {
      //  printf("ici \n");
      mpq_set_num(res,r1);
      mpq_set_den(res,t1);
      ret=0;
      //mpq_out_str(stdout,10,res);printf("\n");
    }
  else
    {
      mpq_set_si(res,-0,1);
      ret=1;
      //printf("je suis pas arrive a reconstruire un nombre\n");
      //mpz_out_str(stdout,10,m);
      //printf("\n");
    }
  mpz_clear(N);
  mpz_clear(r0);
  mpz_clear(r1);
  mpz_clear(t0);
  mpz_clear(t1);
  mpz_clear(q);
  mpz_clear(tmp);
  return ret;
}