Sunday, June 10, 2012

Extended GCD algorithm (Extended Euclidean Algorithm)

I had exercise to implement the extended GCD

The aim of this algorithm is to find x,y that satisfies ax + by = gcd(a,b) for any number a,b

The algorithm is as per the text book as below

image

        public static BigInteger[] Extended_GCD(BigInteger A, BigInteger B)
{
BigInteger[] result = new BigInteger[3];
if (A < B) //if A less than B, switch them
{
BigInteger temp = A;
A = B;
B = temp;
}
BigInteger r = B;
BigInteger q = 0;
BigInteger x0 = 1;
BigInteger y0 = 0;
BigInteger x1 = 0;
BigInteger y1 = 1;
BigInteger x = 0, y = 0;
while (r > 1)
{
r = A % B;
q = A / B;
x = x0 - q * x1;
y = y0 - q * y1;
x0 = x1;
y0 = y1;
x1 = x;
y1 = y;
A = B;
B = r;
}
result[0] = r;
result[1] = x;
result[2] = y;
return result;
}