/* * Created on 17.05.2004 * * This program is a solution for exercise 4.5. It implements the extended * euklidean algorithm and computes some inverse in Z/mZ.    *//** * @author Robert * * Implementation of the extended euklidean algorithm. The main part is  * done in the constructor. The class can also be used for invertation. In that case * the parameter b stands for the module n and getXmodN returns x modulo n.  */public class Euklid {	int g, x, y;	int n;		public Euklid(int a, int b) {				n = b;		int k;		//The extended euklidean algorithm starts here		int r[] = {a,b};		int x[] = {1,0};		int y[] = {0,1};		for(k=0; r[(k+1)%2]!=0; ++k) {			int q = r[k%2]/r[(k+1)%2];			r[k%2] = r[k%2] - q*r[(k+1)%2];			x[k%2] = x[k%2] - q*x[(k+1)%2];			y[k%2] = y[k%2] - q*y[(k+1)%2];		}				this.g = r[k%2];		this.x = x[k%2];		this.y = y[k%2];		// ... and ends here. The next line only verifies the result		if (a*this.x+b*this.y!=this.g) {			System.out.println("this should not happen!!");		}	}	public int getG() {		return g;	}		public int getX() {		return x;	}		public int getY() {		return y;	}		public int getXmodN() {		return (x%n>0 ? x%n : x%n+n);	}	public static void main(String[] args) {		Euklid euk1 = new Euklid(3,1000003);		Euklid euk2 = new Euklid(318,1231231237);		Euklid euk3 = new Euklid(321123,1231231237);				System.out.println(euk1.getXmodN());		System.out.println(euk2.getXmodN());		System.out.println(euk3.getXmodN());	}}