Subversion Repositories planix.SVN

#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;

}