euklid.java

欧几里德算法 找出xm+yn=l x,y解

/*
 * 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());
	}
}