Subversion Repositories planix.SVN

Rev

Rev 22 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
#include "os.h"
2 
#include <mp.h>
3 
 
4 
#define iseven(a)	(((a)->p[0] & 1) == 0)
5 
 
6 
// extended binary gcd
7 
//
26 7u83 8 
// For a and b it solves, v = gcd(a,b) and finds x and y s.t.
2 - 9 
// ax + by = v
10 
//
11 
// Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.
12 
void
13 
mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
14 
{
15 
	mpint *u, *A, *B, *C, *D;
16 
	int g;
17 
 
26 7u83 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);
28 
 
2 - 29 
	if(a->sign < 0 || b->sign < 0){
30 
		mpassign(mpzero, v);
31 
		mpassign(mpzero, y);
32 
		mpassign(mpzero, x);
33 
		return;
34 
	}
35 
 
36 
	if(a->top == 0){
37 
		mpassign(b, v);
38 
		mpassign(mpone, y);
39 
		mpassign(mpzero, x);
40 
		return;
41 
	}
42 
	if(b->top == 0){
43 
		mpassign(a, v);
44 
		mpassign(mpone, x);
45 
		mpassign(mpzero, y);
46 
		return;
47 
	}
48 
 
49 
	g = 0;
50 
	a = mpcopy(a);
51 
	b = mpcopy(b);
52 
 
53 
	while(iseven(a) && iseven(b)){
54 
		mpright(a, 1, a);
55 
		mpright(b, 1, b);
56 
		g++;
57 
	}
58 
 
59 
	u = mpcopy(a);
60 
	mpassign(b, v);
61 
	A = mpcopy(mpone);
62 
	B = mpcopy(mpzero);
63 
	C = mpcopy(mpzero);
64 
	D = mpcopy(mpone);
65 
 
66 
	for(;;) {
67 
//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
68 
		while(iseven(u)){
69 
			mpright(u, 1, u);
70 
			if(!iseven(A) || !iseven(B)) {
71 
				mpadd(A, b, A);
72 
				mpsub(B, a, B);
73 
			}
74 
			mpright(A, 1, A);
75 
			mpright(B, 1, B);
76 
		}
77 
 
78 
//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
79 
		while(iseven(v)){
80 
			mpright(v, 1, v);
81 
			if(!iseven(C) || !iseven(D)) {
82 
				mpadd(C, b, C);
83 
				mpsub(D, a, D);
84 
			}
85 
			mpright(C, 1, C);
86 
			mpright(D, 1, D);
87 
		}
88 
 
89 
//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
90 
		if(mpcmp(u, v) >= 0){
91 
			mpsub(u, v, u);
92 
			mpsub(A, C, A);
93 
			mpsub(B, D, B);
94 
		} else {
95 
			mpsub(v, u, v);
96 
			mpsub(C, A, C);
97 
			mpsub(D, B, D);
98 
		}
99 
 
100 
		if(u->top == 0)
101 
			break;
102 
 
103 
	}
104 
	mpassign(C, x);
105 
	mpassign(D, y);
106 
	mpleft(v, g, v);
107 
 
108 
	mpfree(A);
109 
	mpfree(B);
110 
	mpfree(C);
111 
	mpfree(D);
112 
	mpfree(u);
113 
	mpfree(a);
114 
	mpfree(b);
115 
}