Bignum expmod(Bignum r, Bignum nn, const Bignum &n)
{
//Old, too slow with big numbers...
/*Bignum rr=r;

	while (!((--nn).isZero())) {
		rr*=r;
		while (rr>=n)
			rr-=n;
	}

return rr;*/
// On passe de 17 a 12 secondes pour un nombre de 16 bits ...
Bignum rr=1;

	while (!(nn.isZero())) {
	if (nn.ps->dt[0]&1 == 1)
		rr*=r;
		while (rr>=n)
			rr-=n;
	r*=r;
	while (r>=n)
		r-=n;
	nn>>=1;
	}

return rr;
}

inline isPrime(const Bignum &n)
{
return expmod((Bignum)2,n-(Bignum)1,n)==(Bignum)1;
}

Bignum alea(int s)
{
Bignum r;

r.ext(s+1);
for (int i=0;i<s;i++)
	r.ps->dt[i]=rand()&255;
r.ps->dt[s]=0;
r.strip();
return r;
}

void create_keys(Bignum &n, Bignum &d, Bignum &e)
{
Bignum p,q,phi;

while (p=alea(1/**/), !isPrime(p))
	;
while (q=alea(1/**/), !isPrime(q))
	;

phi=(p-(Bignum)1)*(q-(Bignum)1);

while (e=alea(1), (phi%e).isZero())
	;
//determiner d en fonction de e et phi.
n=p*q;
}

////////////////////////////////////
void update(int *un, int *vn, int q)
{
int tn;

tn=*un-*vn * q;
*un = *vn;
*vn = tn;
}

// a exp(-1) = x (mod n)
// return gcd(x,n) u*u1 v*u2;

int ext_euc(int u, int v, int *u1_out, int *u2_out)
{
int u1=1;
int u3=u;
int v1=0;
int v3=v;
int q;

while (v3>0) {
	q=u3/v3;
	update(&u1,&v1,q);
	update(&u3,&v3,q);
}

*u1_out=u1;
*u2_out=(u3 - u1 * u) / v;
return u3;
}