20060303a

1 files changed, 106 insertions, 0 deletions

diff --git a/libmp/port/mpextendedgcd.c b/libmp/port/mpextendedgcd.c
new file mode 100644
index 00000000..413a05c2
--- /dev/null
+++ b/libmp/port/mpextendedgcd.c
@@ -0,0 +1,106 @@
+#include "os.h"
+#include <mp.h>
+
+#define iseven(a)	(((a)->p[0] & 1) == 0)
+
+// extended binary gcd
+//
+// For a anv b it solves, v = gcd(a,b) and finds x and y s.t.
+// ax + by = v
+//
+// Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.  
+void
+mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
+{
+	mpint *u, *A, *B, *C, *D;
+	int g;
+
+	if(a->sign < 0 || b->sign < 0){
+		mpassign(mpzero, v);
+		mpassign(mpzero, y);
+		mpassign(mpzero, x);
+		return;
+	}
+
+	if(a->top == 0){
+		mpassign(b, v);
+		mpassign(mpone, y);
+		mpassign(mpzero, x);
+		return;
+	}
+	if(b->top == 0){
+		mpassign(a, v);
+		mpassign(mpone, x);
+		mpassign(mpzero, y);
+		return;
+	}
+
+	g = 0;
+	a = mpcopy(a);
+	b = mpcopy(b);
+
+	while(iseven(a) && iseven(b)){
+		mpright(a, 1, a);
+		mpright(b, 1, b);
+		g++;
+	}
+
+	u = mpcopy(a);
+	mpassign(b, v);
+	A = mpcopy(mpone);
+	B = mpcopy(mpzero);
+	C = mpcopy(mpzero);
+	D = mpcopy(mpone);
+
+	for(;;) {
+//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
+		while(iseven(u)){
+			mpright(u, 1, u);
+			if(!iseven(A) || !iseven(B)) {
+				mpadd(A, b, A);
+				mpsub(B, a, B);
+			}
+			mpright(A, 1, A);
+			mpright(B, 1, B);
+		}
+	
+//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
+		while(iseven(v)){
+			mpright(v, 1, v);
+			if(!iseven(C) || !iseven(D)) {
+				mpadd(C, b, C);
+				mpsub(D, a, D);
+			}
+			mpright(C, 1, C);
+			mpright(D, 1, D);
+		}
+	
+//		print("%B %B %B %B %B %B\n", u, v, A, B, C, D);
+		if(mpcmp(u, v) >= 0){
+			mpsub(u, v, u);
+			mpsub(A, C, A);
+			mpsub(B, D, B);
+		} else {
+			mpsub(v, u, v);
+			mpsub(C, A, C);
+			mpsub(D, B, D);
+		}
+
+		if(u->top == 0)
+			break;
+
+	}
+	mpassign(C, x);
+	mpassign(D, y);
+	mpleft(v, g, v);
+
+	mpfree(A);
+	mpfree(B);
+	mpfree(C);
+	mpfree(D);
+	mpfree(u);
+	mpfree(a);
+	mpfree(b);
+
+	return;
+}