Subversion Repositories planix.SVN

Rev

Rev 22 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 22 Rev 26
Line 3... Line 3...
3 
 
 3 
 
4 
#define iseven(a)	(((a)->p[0] & 1) == 0)
 4 
#define iseven(a)	(((a)->p[0] & 1) == 0)
5 
 
 5 
 
6 
// extended binary gcd
 6 
// extended binary gcd
7 
//
 7 
//
8 
// For a anv b it solves, v = gcd(a,b) and finds x and y s.t.
 8 
// For a and b it solves, v = gcd(a,b) and finds x and y s.t.
9 
// ax + by = v
 9 
// ax + by = v
10 
//
 10 
//
11 
// Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.
11 
// Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.
12 
void
 12 
void
13 
mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
 13 
mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
14 
{
 14 
{
15 
	mpint *u, *A, *B, *C, *D;
 15 
	mpint *u, *A, *B, *C, *D;
16 
	int g;
 16 
	int g;
- 
 
 17 
 
- 
 
 18 
	if(v == nil){
- 
 
 19 
		v = mpnew(0);
- 
 
 20 
		mpextendedgcd(a, b, v, x, y);
- 
 
 21 
		mpfree(v);
- 
 
 22 
		return;
- 
 
 23 
	}
- 
 
 24 
	assert(x == nil || (x->flags & MPtimesafe) == 0);
- 
 
 25 
	assert(y == nil || (y->flags & MPtimesafe) == 0);
- 
 
 26 
	assert((a->flags&b->flags) & MPnorm);
- 
 
 27 
	assert(((a->flags|b->flags|v->flags) & MPtimesafe) == 0);
17 
 
 28 
 
18 
	if(a->sign < 0 || b->sign < 0){
 29 
	if(a->sign < 0 || b->sign < 0){
19 
		mpassign(mpzero, v);
 30 
		mpassign(mpzero, v);
20 
		mpassign(mpzero, y);
 31 
		mpassign(mpzero, y);
21 
		mpassign(mpzero, x);
 32 
		mpassign(mpzero, x);
Line 99... Line 110...
99 
	mpfree(C);
 110 
	mpfree(C);
100 
	mpfree(D);
 111 
	mpfree(D);
101 
	mpfree(u);
 112 
	mpfree(u);
102 
	mpfree(a);
 113 
	mpfree(a);
103 
	mpfree(b);
 114 
	mpfree(b);
104 
 
 - 
 
105 
	return;
 - 
 
106 
}
 115 
}