include/borderbasix/reconstruct.cc File Reference

Functions

void chinese (mpz_t res, const mpz_t r1, const mpz_t m1, const mpz_t r2, const mpz_t m2)
int reconstruct (mpq_t res, const mpz_t u, const mpz_t m)

Function Documentation

void chinese	(	mpz_t	res,
		const mpz_t	r1,
		const mpz_t	m1,
		const mpz_t	r2,
		const mpz_t	m2
	)

Definition at line 1 of file reconstruct.cc.

00004 {
00005   mpz_t tmpres;
00006   int swap=1;
00007   mpz_t bez1_1,bez1_2;
00008   mpz_t bez2_1,bez2_2;
00009   mpz_t a,b;
00010   mpz_t q;
00011   mpz_init(tmpres);
00012   mpz_init(q);
00013   mpz_init_set(a,m1);
00014   mpz_init_set(b,m2);
00015   mpz_init_set_si(bez1_1,1);
00016   mpz_init_set_si(bez1_2,0);
00017   mpz_init_set_si(bez2_1,0);
00018   mpz_init_set_si(bez2_2,1);
00019   
00020   if (mpz_cmp(a,b)<0)
00021     {
00022         mpz_swap(a,b);
00023         mpz_swap(bez1_1,bez2_1);
00024         mpz_swap(bez1_2,bez2_2);
00025         swap*=-1;
00026       }
00027   for(;mpz_cmp_si(b,1);)
00028   {
00029     
00030     mpz_tdiv_qr(q,a,a,b);
00031     mpz_submul(bez1_1,bez2_1,q);
00032     mpz_submul(bez1_2,bez2_2,q);
00033     swap*=-1;
00034     mpz_swap(a,b);
00035     mpz_swap(bez1_1,bez2_1);
00036     mpz_swap(bez1_2,bez2_2);
00037   }
00038   mpz_mul(tmpres,bez2_2,m2);
00039   mpz_mul(tmpres,tmpres,r1);
00040   mpz_mul(q,bez2_1,m1);
00041   mpz_mul(q,q,r2);
00042   mpz_add(tmpres,tmpres,q);
00043   mpz_mul(q,m1,m2);
00044   mpz_mod(tmpres,tmpres,q);
00045   
00046   mpz_set(res,tmpres);
00047   mpz_clear(tmpres);
00048   mpz_clear(q);
00049   mpz_clear(bez1_1);
00050   mpz_clear(bez1_2);
00051   mpz_clear(bez2_1);
00052   mpz_clear(bez2_2);
00053   mpz_clear(a);
00054   mpz_clear(b);
00055   
00056 }

int reconstruct	(	mpq_t	res,
		const mpz_t	u,
		const mpz_t	m
	)

Definition at line 58 of file reconstruct.cc.

00059 {
00060   int ret=-1;
00061   mpz_t N;
00062   mpz_t r0,t0;
00063   mpz_t r1,t1;
00064   mpz_t q,tmp;
00065   mpz_init_set(N,m);
00066   mpz_fdiv_q_ui(N,N,2);
00067   mpz_sqrt(N,N);
00068   mpz_init_set(r0,m);
00069   mpz_init_set(r1,u);
00070   mpz_mod(r1,u,m);
00071   mpz_init(t0);
00072   mpz_init_set_ui(t1,1);
00073   mpz_init(q);
00074   mpz_init(tmp);
00075   //printf(" N ");  mpz_out_str(stdout,10,N);printf("\n");
00076   while(mpz_cmp(r1,N)>0)
00077     {
00078       //  printf("passage\n");
00079       mpz_fdiv_q(q,r0,r1);
00080       mpz_set(tmp,r1);
00081       //r1=r0-q*r1;
00082       mpz_mul(r1,r1,q);
00083       mpz_neg(r1,r1);
00084       mpz_add(r1,r0,r1);
00085       //
00086       mpz_set(r0,tmp);
00087       //
00088       //t1=t0-q*t1;
00089       mpz_set(tmp,t1);
00090       mpz_set(t1,t0);
00091       mpz_submul(t1,q,tmp);
00092       //
00093       //t0=tmp;
00094       mpz_set(t0,tmp);
00095       //printf("t0 ");mpz_out_str(stdout,10,t0);printf("\n");  
00096       //printf("r0 ");mpz_out_str(stdout,10,r0);printf("\n");
00097       //printf("t1 ");mpz_out_str(stdout,10,t1);printf("\n");
00098       //printf("r1 ");mpz_out_str(stdout,10,r1);printf("\n");
00099     }
00100   if(mpz_cmp_si(t1,0)<0)
00101     {
00102       //t1=-1*t1;
00103       mpz_neg(t1,t1);
00104       //r1=-1*r1;
00105       mpz_neg(r1,r1);
00106     }
00107   mpz_gcd(tmp,r1,t1);
00108   if((mpz_cmp(t1,N)<0) && (mpz_cmp_si(tmp,1)==0))
00109     {
00110       //  printf("ici \n");
00111       mpq_set_num(res,r1);
00112       mpq_set_den(res,t1);
00113       ret=0;
00114       //mpq_out_str(stdout,10,res);printf("\n");
00115     }
00116   else
00117     {
00118       mpq_set_si(res,-0,1);
00119       ret=1;
00120       //printf("je suis pas arrive a reconstruire un nombre\n");
00121       //mpz_out_str(stdout,10,m);
00122       //printf("\n");
00123     }
00124   mpz_clear(N);
00125   mpz_clear(r0);
00126   mpz_clear(r1);
00127   mpz_clear(t0);
00128   mpz_clear(t1);
00129   mpz_clear(q);
00130   mpz_clear(tmp);
00131   return ret;
00132 }