Cryptography, Extended Euclidian Algorithm (Java)

Merasa banyak tertolong dari sharing2 segala macem di internet, sebagai Student yg akan selalu membutuhkan pertolongan dari Share2 di internet utk menunjang Kuliah akhirnya memutuskan utk share sesuatu jg.

Salah satu tugas dari matakuliah Cryptography tema Extended Euclidian Algorithm (EEA). Utk detail teori apa itu EEA bisa dibaca di banyak literatur, atau bisa tanya mas google yg mungkin nanti akan dilanjutkan ke alamat mbak Wikipedia. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

yg ingin saya share kali ini adalah EEA dlm program Java, sebagai alternativ lain dari yg sudah ada di internet...:-D

sssttt....ini salah satu bahan lab praktikum 1 di mata kuliah ini. sapa tau ada temen (adik kelas) yg kuliah di tempat dan jurusan yg sama dg saya (lihat profil).

monggo: (sebelumnya minta maaf dulu, saya cuman programmer amatir)

import java.math.BigInteger;


public class EuclAlg{

BigInteger a;
BigInteger b;
BigInteger x;
BigInteger y;

//Konstruktor
public EuclAlg (BigInteger A, BigInteger B)
{
a = A;
b = B;
x = new BigInteger("0");
y = new BigInteger("0");
}

/**
* Methoden: Algoritma EEA jalan disini
* gcd(m,n) = mx + ny
* hasilnya adalah x dan y
* @param m
* @param n
*
*/

public void rechnen(BigInteger m, BigInteger n)
{
int c;
BigInteger Q = new BigInteger("0"); //Quotient
BigInteger R = new BigInteger("0"); //Rest
BigInteger B = new BigInteger("0"); //Var. Bilangan yg lebih besar
BigInteger S = new BigInteger("0"); //Var. Bilangan yg lebih kecil


//komponen x & y
BigInteger x1 = new BigInteger("1");
BigInteger y1 = new BigInteger("0");
BigInteger x2 = new BigInteger("0");
BigInteger y2 = new BigInteger("1");
BigInteger xR = new BigInteger("0");
BigInteger yR = new BigInteger("0");

// pendefinisian, bilangan mana yg lebih besar(B) atau kecil(S)
//*************************************************************
c = m.compareTo(n); // -1 -> (m (m>n)

if(c>=0)
{
B = m;
S = n;
}

if (c<0)
{
B = n;
S = m;
}
//***************************************************************

while(true)
{
Q = B.divide(S);
R = B.mod(S);

if (R.compareTo(new BigInteger("0")) == 0)
break;

B = S;
S = R;

xR = x1.subtract(Q.multiply(x2));
yR = y1.subtract(Q.multiply(y2));
x1 = x2;
x2 = xR;
y1 = y2;
y2 = yR;
}



if(c>=0)
{
x = x2;
y = y2;
}

if(c<0)
{
x = y2;
y = x2;
}
}

/**
*
* @return x
*
*/

public BigInteger getX()
{
return x;
}

/**
*
* @return y
*
*/

public BigInteger getY()
{
return y;
}

/**
*
* @return gcd(a,b)
*
*/

public BigInteger getGcd()
{
return a.gcd(b);
}
}

Program diatas saya formulasi berdasarkan Tabel berikut (dari Wikipedia):



Tabel diatas menyelesaikan masalah berikut:
a = 120
b = 23

gcd(a,b) = ax + by.

hasil yg dicapai adalah gcd(a,b), x dan y.

EEA diimplementasikan salah satunya di Chinese Remainder Theorem.

Semoga bisa membantu....